from math import sqrt
import math
from PIL import Image, ImageDraw
from IPython.display import display
import pandas as pd

import numpy as np
import matplotlib.pyplot as plt
import time
import random

# Taille de l'image
W, H = 200, 200 # 2x2 carrés, chaque carré fait 100x100

# Définition des couleurs RGB que va contenir notre image
colors = [(255, 192, 203),     # Rose
    (0, 255, 0),     # Vert
    (0, 0, 255),     # Bleu
    (255, 255, 0)]    # Jaune


# Créer une nouvelle image RGB blanche
im_test = Image.new('RGB', (W, H), color=(255, 255, 255))
draw = ImageDraw.Draw(im_test)

# Dessiner les 4 carrés
carre = W // 2
positions = [
    (0, 0),              # en haut à gauche
    (carre, 0),          # en haut à droite
    (0, carre),          # en bas à gauche
    (carre, carre) # en bas à droite
]

for i, (x, y) in enumerate(positions):
    draw.rectangle([x, y, x + carre, y + carre], fill=colors[i])

# Sauvegarde de l'image au format PNG
im_test.save("quatre_carres.png")
display(im_test)

# Identification de toutes les couleurs de l'image et de leur fréquence
# Pour cela, on utilisera un dictionnaire qui stockera un tuple de couleurs pour la clé et la fréquence associée (le nombre de fois qu'on la retrouve dans l'image).
def couleurs_presentes(im):
    """
    Analyse les couleurs présentes dans une image et calcule leur fréquence.
    Parcourt chaque pixel de l'image fournie et recense toutes les couleurs (sous forme de tuples RGB), en comptant le nombre de fois où chaque couleur apparaît.

    Args :
        im (PIL.Image.Image) : L'image à analyser.

    Returns :
        dict : Un dictionnaire où les clés sont des tuples représentant les couleurs RGB,
               et les valeurs sont des entiers représentant la fréquence d'apparition de chaque couleur.
    """
    D = {}
    W, H = im.size
    px = im.load()

    # comptage des couleurs
    for i in range(W):
        for j in range(H):
            r,g,b = px[i, j] # on récupère la couleur de chaque pixel
            if (r,g,b) in D :
                D[(r,g,b)] += 1 # si la couleur du pixel a déjà été vue dans une autre partie de l'image, on augmente sa fréquence de 1
            else:
                D[(r,g,b)] = 1 # sinon, on l'ajoute au dictionnaire et on fixe son nombre de vue à 1 pour commencer
    return D

dico_couleurs = couleurs_presentes(im_test)
print("Couleurs présentes et fréquences d'apparition :", dico_couleurs,"\n")

print("Nombre de couleurs différentes présentes dans le dégradé de couleurs :", len(dico_couleurs))

Couleurs présentes et fréquences d'apparition : {(255, 192, 203): 10000, (0, 0, 255): 10000, (0, 255, 0): 10000, (255, 255, 0): 10000}

Nombre de couleurs différentes présentes dans le dégradé de couleurs : 4

def afficher_palette(palette):
    """
    Affiche une palette de couleurs sous forme de bandeau horizontal.
    Crée une image composée de rectangles colorés, chacun représentant une couleur issue de la palette.
    Chaque rectangle a la même largeur et est dessiné côte à côte pour former un bandeau.

    Args :
        palette (list): Une liste de tuples où chaque élément est de la forme (couleur, fréquence),
                        avec couleur un tuple RGB (R, G, B). La fréquence est ignorée dans cette fonction.

    Returns :
        None : Affiche l'image dans l'environnement Jupyter via `display()`, mais ne retourne rien.
    """
    # Dimensions de la palette qui s'affichera à l ecran
    largeur_couleur = 500
    hauteur = 100
    k = len(palette)
    largeur = largeur_couleur * k

    # Création d'une image blanche
    bandeau = Image.new("RGB", (largeur, hauteur), "white")
    draw = ImageDraw.Draw(bandeau)

    # Remplissage avec les couleurs
    for i, (couleur, _) in enumerate(palette):
        x0 = i * largeur_couleur
        x1 = x0 + largeur_couleur
        draw.rectangle([x0, 0, x1, hauteur], fill=couleur)

    display(bandeau)

# On récupère uniquement les tuples rgb de notre liste de couleurs
palette_test = list(dico_couleurs.items())
print(palette_test)

# On affiche la palette avec notre fonction
afficher_palette(palette_test)

[((255, 192, 203), 10000), ((0, 0, 255), 10000), ((0, 255, 0), 10000), ((255, 255, 0), 10000)]

def recoloriage(img, palette, choix_distance):
    """
    Recolore une image en associant chaque pixel à la couleur la plus proche dans une palette donnée.
    Pour chaque pixel de l'image d'origine, la fonction calcule la distance entre sa couleur et toutes les couleurs de la palette. Elle remplace ensuite la couleur du pixel par celle de la palette ayant la distance minimale.

    Args :
        img (PIL.Image.Image) : L'image à recolorier.
        palette (list) : Une liste de tuples (couleur, fréquence), où `couleur` est un tuple RGB.
        choix_distance (function) : Une fonction prenant deux tuples RGB et retournant une distance numérique entre ces deux couleurs (ex. distance euclidienne, Manhattan, etc.).

    Returns :
        PIL.Image.Image : Une nouvelle image recoloriée, où chaque pixel est remplacé par la couleur la plus proche dans la palette.
    """
    W, H = img.size
    im_recolored = Image.new("RGB", (W, H))  # création de l'image en sortie
    px_new = im_recolored.load()
    px = img.load()

    for i in range(W):
        for j in range(H):
            indice = 0
            distance_opt = choix_distance(palette[0][0], px[i, j])  # distance avec la première couleur de la palette
            for m in range(len(palette)):
                distance = choix_distance(palette[m][0], px[i, j])
                if distance < distance_opt:
                    distance_opt = distance
                    indice = m
            px_new[i, j] = palette[indice][0]

    return im_recolored  # on retourne l'image recoloriée

# création de la fonction distance euclidienne
def distance_euclid(c1: tuple, c2: tuple) -> float:
    """
    Calcule la distance euclidienne entre deux couleurs RGB.
    Cette distance est définie comme la racine carrée de la somme des carrés des différences entre les composantes rouges, vertes et bleues des deux couleurs.

    Args :
        c1 (tuple) : Première couleur, sous forme de tuple (R, G, B).
        c2 (tuple) : Deuxième couleur, sous forme de tuple (R, G, B).

    Returns :
        float : La distance euclidienne entre les deux couleurs.
    """
    (r1,g1,b1) = c1
    (r2,g2,b2) = c2
    return sqrt((r2-r1)**2 + (g2-g1)**2 + (b2-b1)**2)

# On choisit ici une palette d'abord de 4 couleurs et ensuite de 3 couleurs afin de voir comment fonctionne notre algorithme
palette_test_2 = palette_test[0:3] # palette de 3 couleurs : rose, vert et bleu

# Affichage de l'image recoloriée
img_recoloriee_test = recoloriage(im_test, palette_test, distance_euclid) # image recoloriée avec palette de 4 couleurs
img_recoloriee_test_2 = recoloriage(im_test, palette_test_2, distance_euclid) # image recoloriée avec palette de 3 couleurs

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(im_test)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(img_recoloriee_test)
axs[1].set_title("Image recoloriée avec palette de 4 couleurs \n(test 1)")
axs[1].axis('off')

axs[2].imshow(img_recoloriee_test_2)
axs[2].set_title("Image recoloriée avec palette de 3 couleurs \n(test 2)")
axs[2].axis('off')

plt.tight_layout()
plt.show()

def score(image_originale, image_recoloriee, choix_distance=distance_euclid):
    """
    Évalue la qualité du recoloriage en comparant chaque pixel de l'image d'origine avec celui de l'image recoloriée.

    La fonction calcule trois mesures d'erreur :
    - L'erreur totale : somme des distances entre chaque paire de pixels (original vs recolorié).
    - L'erreur moyenne : moyenne des distances par pixel.
    - Le pourcentage d'erreur : erreur moyenne normalisée par la distance maximale possible entre deux couleurs RGB.

    Paramètres :
        image_originale (PIL.Image.Image) : L'image d'origine non modifiée.
        image_recoloriee (PIL.Image.Image) : L'image générée après recoloriage.
        choix_distance (function) : Fonction utilisée pour calculer la distance entre deux couleurs.
                                    Par défaut, utilise la distance euclidienne.

    Retour :
        dict : Un dictionnaire contenant :
            - "erreur_totale" (float) : Somme totale des distances.
            - "erreur_moyenne" (float) : Moyenne des distances par pixel.
            - "pourcentage_erreur" (float) : Erreur normalisée entre 0 et 100 (%).
    """
    # On récupère les élements de l'image
    largeur, hauteur = image_originale.size
    pixels_orig = image_originale.load()
    pixels_reco = image_recoloriee.load()

    erreur_totale = 0

    # Parcours de tous les pixels de l'image
    for i in range(largeur):
        for j in range(hauteur):
            couleur1 = pixels_orig[i, j]         # pixel original
            couleur2 = pixels_reco[i, j]         # pixel recolorié
            erreur_totale += choix_distance(couleur1, couleur2)

    # Distance maximale possible entre deux couleurs RGB (du noir au blanc)
    distance_max = choix_distance((0,0,0),(255,255,255))

    # Erreur moyenne par pixel
    erreur_moyenne = erreur_totale / (largeur * hauteur)

    # Erreur normalisée en pourcentage
    pourcentage_erreur = (erreur_moyenne / distance_max) * 100

    return {
        "erreur_totale": round(erreur_totale, 2),
        "erreur_moyenne": round(erreur_moyenne, 2),
        "pourcentage_erreur": round(pourcentage_erreur, 2)
    }

resultats = score(im_test, img_recoloriee_test, distance_euclid)
print("Le score du test 1 avec la palette de 4 couleurs \n")
print(f"Erreur globale totale : {resultats['erreur_totale']}")
print(f"Erreur moyenne par pixel : {resultats['erreur_moyenne']}")
print(f"Pourcentage d'erreur : {resultats['pourcentage_erreur']} % \n\n")

print("Le score du test 2 avec la palette de 3 couleurs \n")
resultats = score(im_test, img_recoloriee_test_2, distance_euclid)
print(f"Erreur globale totale : {resultats['erreur_totale']}")
print(f"Erreur moyenne par pixel : {resultats['erreur_moyenne']}")
print(f"Pourcentage d'erreur : {resultats['pourcentage_erreur']} %")

Le score du test 1 avec la palette de 4 couleurs

Erreur globale totale : 0.0
Erreur moyenne par pixel : 0.0
Pourcentage d'erreur : 0.0 %


Le score du test 2 avec la palette de 3 couleurs

Erreur globale totale : 2125511.7
Erreur moyenne par pixel : 53.14
Pourcentage d'erreur : 12.03 %

def difference(image_originale, image_recoloriee, choix_distance):
    """
    Génère une image représentant les différences entre une image originale et une image recoloriée.
    Chaque pixel de l'image retournée est coloré en rouge, avec une intensité proportionnelle à la distance entre les couleurs des pixels correspondants dans les deux images.
    Plus la différence est grande, plus le rouge est intense (max 255). Cette image permet de visualiser les zones où le recoloriage est le moins fidèle.

    Paramètres :
        image_originale (PIL.Image.Image) : L'image de référence (non modifiée).
        image_recoloriee (PIL.Image.Image) : L'image issue du recoloriage.
        choix_distance (function) : Fonction qui calcule une distance entre deux couleurs RGB.

    Retour :
        PIL.Image.Image : Une image en tons de rouge représentant l'erreur, redimensionnée à 50 % pour un affichage plus compact.
    """
    largeur = min(image_originale.width, image_recoloriee.width)
    hauteur = min(image_originale.height, image_recoloriee.height)

    px_orig = image_originale.load()
    px_reco = image_recoloriee.load()

    # Nouvelle image pour visualiser l’erreur (rouge = erreur forte)
    image_erreur = Image.new("RGB", (largeur, hauteur))
    px_error = image_erreur.load()

    for i in range(largeur):
        for j in range(hauteur):
            c1 = px_orig[i, j]       # couleur originale
            c2 = px_reco[i, j]       # couleur recoloriée
            d = int(choix_distance(c1, c2))  # distance euclidienne
            d = min(255, d)          # intensité maximale = 255

            px_error[i, j] = (d, 0, 0)  # rouge = différence

    return image_erreur.resize((largeur//2,hauteur//2))

diff_test = difference(im_test, img_recoloriee_test, distance_euclid)

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(im_test)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(img_recoloriee_test)
axs[1].set_title("Image recoloriée")
axs[1].axis('off')

axs[2].imshow(diff_test)
axs[2].set_title("Différence")
axs[2].axis('off')

plt.tight_layout()
plt.show()

# Affichage de l'image recoloriée
diff_test_2 = difference(im_test, img_recoloriee_test_2, distance_euclid)

fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(im_test)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(img_recoloriee_test_2)
axs[1].set_title("Image recoloriée")
axs[1].axis('off')

axs[2].imshow(diff_test_2)
axs[2].set_title("Différence")
axs[2].axis('off')

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from PIL import Image


def affichage_difference_3D(image_originale, image_recoloriee, choix_distance = distance_euclid):
    """
    Affiche visuellement les différences entre une image originale et une image recoloriée, à la fois en 2D (intensité rouge) et en 3D (barres de hauteur proportionnelle à l'erreur).

    La fonction calcule la distance entre les couleurs correspondantes dans les deux images à chaque pixel. Elle produit :
    - une image 2D montrant les erreurs en rouge (plus la différence est forte, plus le rouge est intense),
    - un graphique 3D (bar3D) où la hauteur de chaque barre représente l'intensité de la différence.

    Paramètres :
        image_originale (PIL.Image.Image) : L'image de référence à comparer.
        image_recoloriee (PIL.Image.Image) : L'image recoloriée à analyser.
        choix_distance (function, optionnel) : Fonction pour calculer la distance entre deux couleurs RGB. Par défaut, utilise la distance euclidienne.

    Retour :
        None : Affiche les visualisations à l'écran, mais ne retourne rien.
    """
    largeur = min(image_originale.width, image_recoloriee.width)
    hauteur = min(image_originale.height, image_recoloriee.height)

    px_orig = image_originale.load()
    px_reco = image_recoloriee.load()

    image_erreur = Image.new("RGB", (largeur, hauteur))
    px_error = image_erreur.load()

# Matrices de 0 créée
    distances = np.zeros((hauteur, largeur))

    for i in range(largeur):
        for j in range(hauteur):
            c1 = px_orig[i, j]
            c2 = px_reco[i, j]
            d = choix_distance(c1, c2)
            distances[j, i] = d  # Note: row = y = j, column = x = i

            d_int = int(min(255, d))
            px_error[i, j] = (d_int, 0, 0)

    # Affiche l'image erreur en 2D
    plt.figure(figsize=(6, 6))
    plt.title("Image des erreurs (rouge = forte différence)")
    plt.imshow(image_erreur.resize((largeur//2, hauteur//2)))
    plt.axis('off')
    plt.show()

    # Plot 3D
    x = np.arange(0, largeur)
    y = np.arange(0, hauteur)
    x, y = np.meshgrid(x, y)
    z = np.zeros_like(distances)
    dx = dy = 1
    dz = distances

    fig = plt.figure(figsize=(10, 7))
    ax = fig.add_subplot(111, projection='3d')
    ax.bar3d(x.ravel(), y.ravel(), z.ravel(), dx, dy, dz.ravel(), shade=True, color='red')
    ax.set_title("3D des erreurs (hauteur = intensité de la différence)")
    ax.set_xlabel("X")
    ax.set_ylabel("Y")
    ax.set_zlabel("Erreur")
    plt.show()

im_test_rainbow = Image.open("rainbow.png")
im_test_rainbow = im_test_rainbow.convert("RGB")  # important pour bien avoir 3 couleurs
px = im_test_rainbow.load()

W, H = im_test_rainbow.size          # taille de l'image

#im = im.resize((W//2, H//2))

# redimensionnement de l'image
display(im_test_rainbow.resize((W//2, H//2)))             # on affiche l'image dans la cellule

dico_couleurs_rainbow = couleurs_presentes(im_test_rainbow)
palette_test_rainbow = list(dico_couleurs.items())
palette_test_rainbow = palette_test_rainbow[0:7]

img_recoloriee_test_rainbow = recoloriage(im_test_rainbow, palette_test_rainbow, distance_euclid)
# On affiche notre image des erreurs : plus c'est rouge et plus notre recoloriage est mauvais dans cet endroit
affichage_difference_3D(im_test_rainbow, img_recoloriee_test_rainbow, distance_euclid)

# Génération d'une image de taille variable avec des couleurs aléatoires
def genere_img(W, H):
    """
    Génère une image RGB aléatoire de dimensions spécifiées.
    Chaque pixel de l'image est attribué à une couleur aléatoire, dont les composantes rouge, verte et bleue sont tirées uniformément entre 0 et 255. Cela permet de créer une image de test variée et non structurée.

    Paramètres :
        W (int) : Largeur de l'image (en pixels).
        H (int) : Hauteur de l'image (en pixels).

    Retour :
        PIL.Image.Image : Une image RGB de dimensions (W x H) remplie de couleurs aléatoires.
    """
    img = Image.new("RGB", (W, H))
    for x in range(W):
        for y in range(H):
            img.putpixel((x, y), tuple(random.randint(0, 255) for _ in range(3)))
    return img

# On choisit arbitrairement de générer une image carrée 100x100
im_aleatoire = genere_img(200,200)
display(im_aleatoire)

def complexite_temporelle(type_algo = "naif", distance=distance_euclid):
     """
    Évalue empiriquement la complexité temporelle d'un algorithme de recoloriage en fonction de la taille de l'image.
    Cette fonction génère des images carrées de tailles croissantes avec des couleurs aléatoires, applique l'algorithme de recoloriage choisi, mesure le temps d'exécution, puis trace une courbe du temps en fonction du nombre total de pixels.

    Paramètres :
        type_algo (str) : Le nom de l'algorithme à tester parmi :
                          - "naif"
                          - "median_cut"
                          - "kmeans"
                          - "fourier_YCbCr"
                          - "octree"
        distance (function) : Fonction utilisée pour calculer la distance entre deux couleurs (par défaut : distance euclidienne).

    Affiche :
        Un graphique matplotlib représentant le temps d'exécution (en secondes) en fonction du nombre total de pixels.
    """

     # Mesure du temps d'exécution
     k=8
     nb_iter=10
     n=math.floor(math.log(k)/math.log(2))

     taille_images = [16, 32, 64, 96, 128, 160, 192, 224, 275, 300, 350, 400]
     temps = []
     for taille in taille_images:
         img = genere_img(taille, taille) # on prendra des images de taille carrée pour simplifier (mais le nombre de pixelx total restera inchangé que
         # l'image soit carrée ou rectangulaire)
         start = time.time() # départ du chronomètre

         if type_algo == "naif":
             img_methode_naive, palette_naive = methode_naive(img, choix_distance,k)
         if type_algo == "median_cut":
             img_median_cut = recoloriage_MedianCut(img, n, choix_distance)
         if type_algo == "kmeans":
            img_k_means = kmeans(img, k, nb_iter, choix_distance)
         if type_algo == "fourier_YCbCr":
             img_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img, mode="YCbCr", k=k)
         if type_algo == "fourier_RGB":
            img_fourier_RGB, palette_RGB = traitement_image_par_mode(img, mode="RGB", k=k)
         if type_algo == "octree":
             img_octree, pallette_octree = image_octree(img, k, choix_distance)

         end = time.time() # arrêt du chronomètre
         temps.append(end - start) # mesure de la durée totale d'exécution

     # Affichage du graphique
     plt.figure(figsize=(10, 5))
     nb_pixels = [x * x for x in taille_images]
     plt.plot(nb_pixels, temps, marker='o', color='blue')
     plt.xlabel("Nombre de pixels présents dans l'image")
     plt.ylabel("Temps d'exécution (en s)")
     plt.title("Temps d'exécution de Median Cut en fonction de la taille de l'image")
     plt.grid()
     plt.show()

#complexite_temporelle("naif", distance_euclid)

def complexite_temp_algos(choix_distance=distance_euclid):
    """
    Compare les temps d'exécution de différents algorithmes de réduction de palette en fonction de la taille de l'image.
    Pour chaque taille spécifiée, une image carrée à couleurs aléatoires est générée une seule fois et utilisée pour tester  plusieurs algorithmes de recoloriage. Le temps d'exécution de chaque algorithme est mesuré, puis un graphique comparatif est affiché pour évaluer leur complexité empirique.

    Paramètres :
        choix_distance (function) : Fonction de distance utilisée pour la comparaison des couleurs (par défaut : distance_euclid).

    Retour :
        list : Une liste contenant la figure matplotlib générée (permet d'enregistrer ou manipuler la figure en dehors de la fonction).

    Affiche :
        Un graphique en ligne comparant les temps d'exécution en fonction du nombre de pixels de l'image.
    """
    k = 8
    nb_iter = 10
    n = math.floor(math.log(k) / math.log(2))
    taille_images = [16, 32, 64, 96, 128, 160, 192, 224, 275, 300, 350, 400]
    nb_pixels = [x * x for x in taille_images]

    # Générer une image par taille, une seule fois
    images_par_taille = {taille: genere_img(taille, taille) for taille in taille_images}

    # Liste des algorithmes avec leur nom
    algos = [
        ("Median Cut", lambda img: recoloriage_MedianCut(img, n, choix_distance)),
        ("Octree", lambda img: image_octree(img, k, choix_distance)),
        ("K-means", lambda img: kmeans(img, k, nb_iter, choix_distance)),
        ("Méthode naïve", lambda img: methode_naive(img, choix_distance, k)),
        ("Fourier YCbCr", lambda img: traitement_image_par_mode(img, mode="YCbCr", k=k)),
        ("Fourier RGB", lambda img: traitement_image_par_mode(img, mode="RGB", k=k)),
    ]

    fig, ax = plt.subplots(figsize=(12, 6))

    # Boucle sur les algos pour mesurer les temps
    for nom, fonction_algo in algos:
        temps = []
        for taille in taille_images:
            img = images_par_taille[taille]
            start = time.time()
            fonction_algo(img)
            end = time.time()
            temps.append(end - start)
        ax.plot(nb_pixels, temps, marker='o', label=nom)

    # Mise en forme du graphique
    ax.set_xlabel("Nombre de pixels présents dans l'image")
    ax.set_ylabel("Temps d'exécution (en s)")
    ax.set_title("Comparaison des temps d'exécution selon la taille de l'image (même image pour tous les algos)")
    ax.grid()
    ax.legend()
    fig.tight_layout()

    return [fig]

from PIL import Image
import matplotlib.pyplot as plt
import random
import math

compteur_ops = {"median_cut": 0, "distance": 0} # compteur global

# Fonctions identiques

def distance_euclid(c1, c2):
    """Calcule la distance euclidienne entre deux coordonnées de couleur.

    Paramètres:
        c1 (tuple): Un tuple représentant la première couleur (R, G, B).
        c2 (tuple): Un tuple représentant la deuxième couleur (R, G, B).

    Retour:
        float: La distance euclidienne entre les deux couleurs.
    """
    compteur_ops["distance"] += 1
    return sum((a - b) ** 2 for a, b in zip(c1, c2)) ** 0.5

def median_cut(pixels, profondeur):
    """Applique l'algorithme de "median cut" pour réduire le nombre de couleurs dans une liste de pixels.

    L'algorithme divise récursivement l'espace colorimétrique en fonction de la médiane
    de la plage de couleurs la plus étendue.

    Paramètres:
        pixels (list): Une liste de tuples représentant les couleurs des pixels (R, G, B).
        profondeur (int): Le nombre de niveaux de division à effectuer.
                         Une profondeur de 0 retourne la couleur moyenne des pixels.

    Retour:
        list: Une liste de tuples représentant la palette de couleurs résultante.
    """
    if profondeur == 0 or len(pixels) == 0:
        r = sum(p[0] for p in pixels) // len(pixels)
        g = sum(p[1] for p in pixels) // len(pixels)
        b = sum(p[2] for p in pixels) // len(pixels)
        compteur_ops["median_cut"] += len(pixels) * 3
        return [(r, g, b)]
    ranges = [(max(p[i] for p in pixels) - min(p[i] for p in pixels), i) for i in range(3)]
    compteur_ops["median_cut"] += len(pixels) * 6
    _, channel = max(ranges)
    pixels.sort(key=lambda x: x[channel])
    compteur_ops["median_cut"] += len(pixels) * math.log2(len(pixels) + 1)
    median = len(pixels) // 2
    return median_cut(pixels[:median], profondeur - 1) + median_cut(pixels[median:], profondeur - 1)

def recoloriage_MedianCut(im, profondeur):
    """Réduit le nombre de couleurs d'une image en utilisant l'algorithme de "median cut".

    Paramètres:
        im (PIL.Image.Image): L'image à recolorier.
        profondeur (int): Le nombre de niveaux de division pour l'algorithme "median cut".
                          Détermine la taille de la palette de couleurs résultante (2^profondeur).

    Retour:
        PIL.Image.Image: Une nouvelle image avec un nombre de couleurs réduit.
    """
    px = im.load()
    W, H = im.size
    pixels = [px[x, y] for y in range(H) for x in range(W)]
    palette = median_cut(pixels, profondeur)
    new_img = Image.new("RGB", im.size)
    for y in range(H):
        for x in range(W):
            originale = px[x, y]
            _ = min(palette, key=lambda c: distance_euclid(originale, c))
    return new_img

def generate_random_image(num_pixels):
    """Génère une image RVB aléatoire avec le nombre de pixels spécifié.

    Paramètres:
        num_pixels (int): Le nombre total de pixels souhaité pour l'image.

    Retour:
        PIL.Image.Image: Une image RVB aléatoire.
    """
    width = int(math.sqrt(num_pixels))
    height = (num_pixels + width - 1) // width  # pour éviter les pertes
    img = Image.new("RGB", (width, height))
    for x in range(width):
        for y in range(height):
            if y * width + x < num_pixels:
                img.putpixel((x, y), tuple(random.randint(0, 255) for _ in range(3)))
    return img

# Mesure sur une plage large de pixels
profondeur = 4
nb_pixels = list(range(1000, 300001, 10000))  # de 1k à 300k par pas de 10k

ops_median_cut = []
ops_distance = []

for n in nb_pixels:
    img = generate_random_image(n)
    compteur_ops = {"median_cut": 0, "distance": 0}
    recoloriage_MedianCut(img, profondeur)
    ops_median_cut.append(compteur_ops["median_cut"])
    ops_distance.append(compteur_ops["distance"])

# Plot
plt.figure(figsize=(12, 6))
plt.plot(nb_pixels, ops_median_cut, label="Opérations Median Cut", color='blue')
plt.plot(nb_pixels, ops_distance, label="Opérations Distance", color='green')
plt.plot(nb_pixels, [n * math.log2(n + 1) for n in nb_pixels], '--', label="O(n log n)", color='orange')
plt.plot(nb_pixels, [n**2 / 1000 for n in nb_pixels], '--', label="O(n²) (rescalée)", color='red')

plt.xlabel("Nombre de pixels")
plt.ylabel("Nombre d'opérations")
plt.title("Complexité expérimentale jusqu'à 300 000 pixels")
plt.legend()
plt.grid(True)
plt.tight_layout()
plt.show()

def distance_euclid(c1: tuple, c2: tuple) -> float:
    """Calcule la distance euclidienne entre deux couleurs représentées par des tuples.

    Paramètres:
        c1 (tuple): Un tuple de trois entiers représentant la première couleur (Rouge, Vert, Bleu).
        c2 (tuple): Un tuple de trois entiers représentant la deuxième couleur (Rouge, Vert, Bleu).

    Retour:
        float: La distance euclidienne entre les deux couleurs.
    """
    (r1,g1,b1) = c1
    (r2,g2,b2) = c2
    return sqrt((r2-r1)**2 + (g2-g1)**2 + (b2-b1)**2)

# test :
rgb1 = (0, 0, 0)
rgb2 = (255, 255, 255)
distance_euclid(rgb1,rgb2)

441.6729559300637

# Même point : distance = 0
assert abs(distance_euclid((50, 0, 0), (50, 0, 0))) < 1e-6, "Erreur : distance entre points identiques doit être 0"

# Déplacement unitaire sur chaque axe
assert abs(distance_euclid((0, 0, 0), (1, 0, 0)) - 1) < 1e-6, "Erreur : distance L* incorrecte"
assert abs(distance_euclid((0, 0, 0), (0, 1, 0)) - 1) < 1e-6, "Erreur : distance a* incorrecte"
assert abs(distance_euclid((0, 0, 0), (0, 0, 1)) - 1) < 1e-6, "Erreur : distance b* incorrecte"

# Distance diagonale simple
d = distance_euclid((0, 0, 0), (1, 1, 1))
assert abs(d - sqrt(3)) < 1e-6, f"Erreur : distance diagonale incorrecte ({d} ≠ {sqrt(3)})"

# Symétrie
p1 = (10, 20, 30)
p2 = (40, 50, 60)
assert abs(distance_euclid(p1, p2) - distance_euclid(p2, p1)) < 1e-6, "Erreur : la distance n'est pas symétrique"

print("Tous les tests de distance euclidienne dans l'espace Lab sont passés avec succès.")

Tous les tests de distance euclidienne dans l'espace Lab sont passés avec succès.

"""
ETAPE 1 : Conversion RGB en coordonnées XYZ
"""

def rgb_en_xyz(r, g, b):
    """Convertit les composantes RGB d'une couleur en coordonnées XYZ.

    Paramètres:
        r (int): La composante rouge (0-255).
        g (int): La composante verte (0-255).
        b (int): La composante bleue (0-255).

    Retour:
        tuple: Un tuple de trois floats représentant les coordonnées XYZ.
    """
    # On commence par normaliser les composantes RGB entre 0 et 1
    r = r / 255.0
    g = g / 255.0
    b = b / 255.0

    # Correction gamma (inverse de la transformation sRGB)
    def gamma(u):
        # Si la composante est supérieure à un seuil, on applique une formule non linéaire
        if u > 0.04045 :
            return ((u + 0.055) / 1.055) ** 2.4
        else :
            return u / 12.92

    # Application de la correction gamma à chaque composante
    r = gamma(r)
    g = gamma(g)
    b = gamma(b)

    # Coefficients basés sur les normes CIE
    x = r * 0.4124 + g * 0.3576 + b * 0.1805
    y = r * 0.2126 + g * 0.7152 + b * 0.0722
    z = r * 0.0193 + g * 0.1192 + b * 0.9505

    return x, y, z


"""
ETAPE 2 : Conversion XYZ en CIELAB
"""
def xyz_en_lab(x, y, z):
    """Convertit les coordonnées XYZ d'une couleur en coordonnées CIELAB.

    Paramètres:
        x (float): La coordonnée X.
        y (float): La coordonnée Y (luminance relative).
        z (float): La coordonnée Z.

    Retour:
        tuple: Un tuple de trois floats représentant les coordonnées CIELAB (L, a, b).
    """

    # Valeurs de référence du blanc D65 (illuminant standard)
    Xn, Yn, Zn = 0.95047, 1.00000, 1.08883

    # On normalise les valeurs XYZ en divisant par les valeurs de référence
    x /= Xn
    y /= Yn
    z /= Zn

    # Fonction f(t) utilisée pour la transformation non linéaire
    def f(t):
        if t > 0.008856: # Si t est suffisamment grand, on prend la racine cubique
            return t ** (1/3)
        else:         # Sinon, on applique une fonction affine
            return (7.787 * t) + (16 / 116)

    # Application de f(t) à chaque composante normalisée
    fx = f(x)
    fy = f(y)
    fz = f(z)

    # Formules finales de conversion XYZ → Lab
    L = 116 * fy - 16      # Luminance
    a = 500 * (fx - fy)    # Différence entre rouge et vert
    b = 200 * (fy - fz)    # Différence entre jaune et bleu

    return L, a, b  # On retourne la couleur en espace Lab


"""
ETAPE 3 : Conversion RGB en Lab
"""
def rgb_en_lab(rgb):
    """Convertit un tuple de composantes RGB en coordonnées CIELAB.

    Paramètres:
        rgb (tuple): Un tuple de trois entiers représentant la couleur (Rouge, Vert, Bleu).

    Retour:
        tuple: Un tuple de trois floats représentant les coordonnées CIELAB (L, a, b).
    """
    # On décompose le tuple (R, G, B)
    x, y, z = rgb_en_xyz(*rgb)
    # On convertit XYZ en Lab
    return xyz_en_lab(x, y, z)

"""
ETAPE 4 : Calcul de la distance euclidienne entre deux couleurs Lab
"""

def distance_lab(rgb1, rgb2): # rgb1 de la forme px[i,j]
    """Calcule la distance euclidienne entre deux couleurs RGB dans l'espace colorimétrique CIELAB.

    Paramètres:
        rgb1 (tuple): Un tuple de trois entiers représentant la première couleur (Rouge, Vert, Bleu).
        rgb2 (tuple): Un tuple de trois entiers représentant la deuxième couleur (Rouge, Vert, Bleu).

    Retour:
        float: La distance euclidienne entre les deux couleurs dans l'espace Lab.
    """
    # On convertit les deux couleurs de RGB vers Lab
    l1,a1,b1 = rgb_en_lab(rgb1)
    l2,a2,b2 = rgb_en_lab(rgb2)
    # On applique la formule de distance euclidienne dans l’espace Lab
    return sqrt((l1-l2)**2 +(a1-a2)**2 + (b1-b2)**2)

# Couleurs identiques : distance nulle
assert abs(distance_lab((255, 0, 0), (255, 0, 0))) < 1e-6, "Erreur : la distance entre deux rouges identiques doit être 0"

# Couleurs très différentes : distance élevée
d_red_blue = distance_lab((255, 0, 0), (0, 0, 255))
assert d_red_blue > 100, f"Erreur : distance rouge / bleu trop faible ({d_red_blue})"

# Noir et blanc : distance maximale (dans les extrêmes de luminance)
d_black_white = distance_lab((0, 0, 0), (255, 255, 255))
assert d_black_white > 100, f"Erreur : distance noir / blanc trop faible ({d_black_white})"

# Couleurs proches : distance faible
d_light_gray = distance_lab((200, 200, 200), (210, 210, 210))
assert d_light_gray < 5, f"Erreur : distance entre gris clairs trop élevée ({d_light_gray})"

# Test symétrie (d(a,b) == d(b,a))
a = (123, 200, 45)
b = (20, 10, 200)
assert abs(distance_lab(a, b) - distance_lab(b, a)) < 1e-6, "Erreur : la distance n'est pas symétrique"

print("Tous les tests de distance ΔE 76 sont passés avec succès")

Tous les tests de distance ΔE 76 sont passés avec succès

from math import sqrt, sin, cos, radians, degrees, atan2, exp

def delta_e_2000(rgb1, rgb2):
    """Calcule la différence de couleur Delta E 2000 entre deux couleurs RGB.

    Cette métrique prend en compte les non-linéarités de la perception humaine
    de la couleur, en utilisant l'espace colorimétrique CIELAB et des corrections
    pour la luminance, la chromaticité et la teinte.

    Paramètres:
        rgb1 (tuple): Un tuple de trois entiers représentant la première couleur (Rouge, Vert, Bleu).
        rgb2 (tuple): Un tuple de trois entiers représentant la deuxième couleur (Rouge, Vert, Bleu).

    Retour:
        float: La différence de couleur Delta E 2000 entre les deux couleurs.
    """
    # Conversion RGB -> Lab
    L1, a1, b1 = rgb_en_lab(rgb1)
    L2, a2, b2 = rgb_en_lab(rgb2)

    """
    Etape 1 : Moyennes et chroma
    """
    moy_L = (L1 + L2) / 2

    # Chroma = √(a² + b²)
    C1 = sqrt(a1**2 + b1**2)
    C2 = sqrt(a2**2 + b2**2)
    moy_C = (C1 + C2) / 2

    """
    Etape 2 : Correction chroma G (facteur de compression de la chroma pour les couleurs vives pour corriger les erreurs perceptuelles)
    """
    G = 0.5 * (1 - sqrt((moy_C**7) / (moy_C**7 + 25**7)))

    """
    Etape 3 : Nouvelles composantes qui permettent de modifier les composantes rouges/vertes (a1 et a2) pour corriger la perception
    """
    a1p = (1 + G) * a1
    a2p = (1 + G) * a2
    C1p = sqrt(a1p**2 + b1**2)
    C2p = sqrt(a2p**2 + b2**2)
    moy_Cp = (C1p + C2p) / 2

    """
    Etape 4 : Calculs d'angle de teinte h
    """
    h1p = degrees(atan2(b1, a1p)) % 360
    h2p = degrees(atan2(b2, a2p)) % 360

    """
    Etape 5 : Différences de teinte : on utilise une distance angulaire corrigée car les teintes sont circulaires (360°)
    """
    delta_hp = h2p - h1p
    if delta_hp > 180:
        delta_hp -= 360
    elif delta_hp < -180:
        delta_hp += 360

    deltaHp = 2 * sqrt(C1p * C2p) * sin(radians(delta_hp / 2))

    """
    Etape 6 : Calcul de la moyenne des delta
    """
    deltaLp = L2 - L1
    deltaCp = C2p - C1p
    moy_Lp = (L1 + L2) / 2

    if abs(h1p - h2p) > 180:
        if h1p + h2p < 360:
            moy_hp = (h1p + h2p + 360) / 2
        else:
            moy_hp = (h1p + h2p - 360) / 2
    else:
        moy_hp = (h1p + h2p) / 2

    """
    Etape 7 : Calcul des pondérations : le coefficient T ajuste la pondération de la teinte selon l'angle moyen
    """
    T = 1 - 0.17 * cos(radians(moy_hp - 30)) \
        + 0.24 * cos(radians(2 * moy_hp)) \
        + 0.32 * cos(radians(3 * moy_hp + 6)) \
        - 0.20 * cos(radians(4 * moy_hp - 63))

    """
    Etape 8 : Facteur de rotation Rt pour corriger une interaction chroma/teinte dans les bleus (zones sensibles à l'oeil humain)
    """
    delta_theta = 30 * exp(-((moy_hp - 275) / 25) ** 2)
    Rc = 2 * sqrt((moy_Cp ** 7) / (moy_Cp ** 7 + 25 ** 7))
    Rt = -sin(radians(2 * delta_theta)) * Rc

    """
    Etape 9 : Facteurs d'échelle pour normaliser les différences L, C, H selon leur importante dans la perception visuelle
    """
    Sl = 1 + (0.015 * (moy_Lp - 50) ** 2) / sqrt(20 + (moy_Lp - 50) ** 2)
    Sc = 1 + 0.045 * moy_Cp
    Sh = 1 + 0.015 * moy_Cp * T

    """
    Etape 10 : Calcul final de la distance
    """
    deltaE = sqrt(
        (deltaLp / Sl) ** 2 +
        (deltaCp / Sc) ** 2 +
        (deltaHp / Sh) ** 2 +
        Rt * (deltaCp / Sc) * (deltaHp / Sh)
    )
    return deltaE

# Couleurs identiques → distance doit être 0
assert abs(delta_e_2000((255, 0, 0), (255, 0, 0))) < 1e-6, "Test rouge-rouge échoué"
assert abs(delta_e_2000((0, 255, 0), (0, 255, 0))) < 1e-6, "Test vert-vert échoué"
assert abs(delta_e_2000((0, 0, 255), (0, 0, 255))) < 1e-6, "Test bleu-bleu échoué"

# Couleurs très proches → distance faible
d1 = delta_e_2000((255, 0, 0), (254, 1, 0))
assert d1 < 2, f"Test couleurs proches échoué, distance = {d1}"
# Couleurs très différentes → distance grande
d2 = delta_e_2000((255, 0, 0), (0, 255, 0))
assert d2 > 40, f"Test rouge-vert échoué, distance = {d2}"

d3 = delta_e_2000((0, 0, 0), (255, 255, 255))
assert d3 > 90, f"Test noir-blanc échoué, distance = {d3}"

print("Tous les tests Delta E 2000 sont passés avec succès")

Tous les tests Delta E 2000 sont passés avec succès

# Création du DataFrame avec les sauts de ligne dans les chaînes
data = {
    "Avantages": [
        "Facile à implémenter\nRapide à calculer",
        "Excellente qualité pour le regroupement de couleurs",
        "Précision pour juger si deux couleurs sont visuellement similaires"
    ],
    "Inconvénients": [
        "Ne correspond pas bien à la perception humaine (on perçoit certaines différences de couleurs plus fortement que d'autres)",
        "Il faut convertir chaque couleur RGB en Lab (plus coûteux)",
        "Plus complexe à implémenter\nMoins intuitif"
    ]
}

index = ["Distance Euclidienne en RGB", "Distance DeltaE76", "Distance DeltaE00"]

df = pd.DataFrame(data, index=index)



# Appliquer le style pour permettre les sauts de ligne visibles
styled_df = df.style.set_properties(**{'white-space': 'pre-wrap'})

# Afficher le DataFrame stylisé avec les retours à la ligne visibles
display(styled_df)

rainbow = Image.open("rainbow.png")
rainbow = rainbow.convert("RGB")  # important pour bien avoir 3 couleurs
px = rainbow.load()

W, H = rainbow.size          # taille de l'image
r, g, b = px[10, 20]    # on récupère un pixel
px[10, 21] = r, g, b    # on change un pixel

#im = im.resize((W//2, H//2))

# redimensionnement de l'image
display(rainbow.resize((W//2, H//2)))             # on affiche l'image dans la cellule

# liste des couleurs présentes dans l'image
dico_couleurs = couleurs_presentes(rainbow)

print("Nombre de couleurs différentes présentes dans le dégradé de couleurs :", len(dico_couleurs))

Nombre de couleurs différentes présentes dans le dégradé de couleurs : 409

def methode_naive(img, choix_distance=distance_euclid, k=8):
    """Applique une méthode naïve de réduction de couleurs à une image. Cette méthode sélectionne les k couleurs les plus fréquentes dans l'image comme palette, puis recolorie l'image en assignant à chaque pixel la couleur la plus proche dans la palette sélectionnée.

    Paramètres:
        img (PIL.Image.Image): L'image à traiter.
        choix_distance (function) : La fonction de distance à utiliser pour comparer les couleurs. Par défaut, `distance_euclid`.
        k (int): Le nombre de couleurs à inclure dans la palette résultante. Par défaut, 8.

    Retour:
        tuple: Un tuple contenant deux éléments :
            - PIL.Image.Image: L'image recoloriée avec la palette réduite.
            - list: La palette de couleurs sélectionnée (une liste de tuples RGB).
    """
    dico_couleurs = couleurs_presentes(img)
    couleurs_triees = sorted(dico_couleurs.items(), key=lambda item: item[1], reverse=True)
    palette_naive = couleurs_triees[0:k]
    image_recoloriee = recoloriage(img,palette_naive,choix_distance)

    return image_recoloriee, palette_naive

# on tri le dictionnaire en fonction des couleurs les plus redondantes dans l'image
couleurs_triees = sorted(dico_couleurs.items(), key=lambda item: item[1], reverse=True)
#print(couleurs_triees)

# on choisit naïvement les 8 couleurs les plus présentes dans l'image
palette_naive = couleurs_triees[0:8]
afficher_palette(palette_naive)

# On affiche notre image recoloriée, en réduisant ses dimensions par deux
rainbow_recoloriee, palette_utilisee = methode_naive(rainbow,distance_euclid,8)

# Affichage
fig, axs = plt.subplots(1, 2, figsize=(15, 3))
axs[0].imshow(rainbow)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(rainbow_recoloriee)
axs[1].set_title("Image recoloriée avec palette de 8 couleurs")
axs[1].axis('off')

plt.tight_layout()
plt.show()

score(rainbow,rainbow_recoloriee, distance_euclid)

{'erreur_totale': 11541133.57,
 'erreur_moyenne': 44.37,
 'pourcentage_erreur': 10.05}

# On affiche notre image des erreurs : plus c'est rouge et plus notre recoloriage est mauvais dans cet endroit
diff = difference(rainbow,rainbow_recoloriee,distance_euclid)

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(rainbow)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(rainbow_recoloriee)
axs[1].set_title("Image recoloriée")
axs[1].axis('off')

axs[2].imshow(diff)
axs[2].set_title("Différence")
axs[2].axis('off')

plt.tight_layout()
plt.show()

# Définition de la nouvelle palette contenant plus de couleurs
k = 30 # on fixe à 30 couleurs arbitrairement
palette_naive_2 = couleurs_triees[0:k]

# On recolorie notre image
rainbow_reco_2 = recoloriage(rainbow,palette_naive_2, distance_euclid)

diff_rainbow = difference(rainbow,rainbow_recoloriee,distance_euclid)

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(rainbow)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(rainbow_reco_2)
axs[1].set_title("Image recoloriée")
axs[1].axis('off')

axs[2].imshow(diff_rainbow)
axs[2].set_title("Différence")
axs[2].axis('off')

plt.tight_layout()
plt.show()

def _median_cut_recursive(pixels, profondeur):
    """Implémentation récursive de l'algorithme "median cut".

    Cette fonction divise récursivement une liste de pixels en deux groupes en fonction de la médiane de la composante de couleur ayant la plus grande plage.
    Le processus continue jusqu'à atteindre la profondeur spécifiée ou qu'il n'y ait plus de pixels.

    Paramètres:
        pixels (list): Une liste de tuples représentant les couleurs des pixels (R, G, B).
        profondeur (int): Le nombre de niveaux de division restants.

    Retour:
        list: Une liste contenant une seule couleur (la moyenne des pixels) lorsque la profondeur est atteinte ou la liste de pixels est vide. Sinon, retourne la concaténation des palettes résultant des deux divisions.
    """
    if profondeur == 0 or len(pixels) == 0:
        r = sum(p[0] for p in pixels) // len(pixels)
        g = sum(p[1] for p in pixels) // len(pixels)
        b = sum(p[2] for p in pixels) // len(pixels)
        return [(r, g, b)]

    # On choisit la composante qui varie le plus
    ranges = [(max(p[i] for p in pixels) - min(p[i] for p in pixels), i) for i in range(3)]
    _, channel = max(ranges)
    pixels.sort(key=lambda x: x[channel])
    median = len(pixels) // 2

    return _median_cut_recursive(pixels[:median], profondeur - 1) + _median_cut_recursive(pixels[median:], profondeur - 1)

def median_cut(image, profondeur):
    """Applique l'algorithme de "median cut" pour générer une palette de couleurs à partir d'une image.
    L'algorithme divise récursivement l'espace colorimétrique de l'image pour créer une palette de taille 2^profondeur.

    Paramètres:
        image (PIL.Image.Image): L'image à partir de laquelle générer la palette.
        profondeur (int): Le nombre de niveaux de division à effectuer.
                         La taille de la palette résultante sera 2^profondeur.

    Retour:
        list: Une liste de tuples représentant la palette de couleurs (R, G, B).
    """
    px = image.load()
    W, H = image.size
    pixels = [px[x, y] for y in range(H) for x in range(W)]
    return _median_cut_recursive(pixels, profondeur)

# On recolorie l'image avec la nouvelle palette de couleurs
def recoloriage_MedianCut(im, profondeur, choix_distance=distance_euclid):
    """Réduit le nombre de couleurs d'une image en utilisant l'algorithme "median cut" pour générer la palette.
    L'image est ensuite recoloriée en assignant à chaque pixel la couleur la plus proche dans la palette générée.

    Paramètres:
        im (PIL.Image.Image): L'image à recolorier.
        profondeur (int): Le nombre de niveaux de division pour l'algorithme "median cut".
                          Détermine la taille de la palette de couleurs résultante (2^profondeur).
        choix_distance (callable, optional): La fonction de distance à utiliser pour
                                            comparer les couleurs. Par défaut, `distance_euclid`.

    Retour:
        PIL.Image.Image: Une nouvelle image avec un nombre de couleurs réduit.
    """
    px = im.load()
    W, H = im.size

    palette = median_cut(im, profondeur)  # on passe directement l'image

    new_img = Image.new("RGB", im.size)
    for y in range(H):
        for x in range(W):
            originale = px[x, y]
            plus_proche = min(palette, key=lambda c: choix_distance(originale, c))
            new_img.putpixel((x, y), plus_proche)

    return new_img

def test_median_cut_profondeur_0(im_test):
    palette = median_cut(im_test, 0)
    assert isinstance(palette, list)  # La sortie doit être une liste
    assert len(palette) == 1          # Il ne doit y avoir qu'une seule couleur (profondeur = 0)
    assert all(isinstance(c, tuple) and len(c) == 3 for c in palette)  # Chaque couleur doit être un tuple (R, G, B)


def test_median_cut_profondeur_2(im_test):
    palette = median_cut(im_test, 2)
    assert len(palette) == 4  # Pour une profondeur 2, on attend 2^2 = 4 couleurs
    assert all(isinstance(c, tuple) and len(c) == 3 for c in palette)  # Chaque élément de la palette doit être un tuple RGB


def test_palette_approximation(im_test):
    palette = median_cut(im_test, 2)
    colors_in_img = set(im_test.getdata())  # On extrait les couleurs réelles de l'image
    for color in colors_in_img:
        assert any(distance_euclid(color, c) < 50 for c in palette)  # Chaque couleur réelle doit avoir une couleur proche dans la palette


def test_recoloriage_taille_identique(im_test):
    recolored = recoloriage_MedianCut(im_test, 2)
    assert recolored.size == im_test.size  # L'image recoloriée doit avoir la même taille que l'originale

def test_recoloriage_couleurs_dans_palette(im_test):
    palette = median_cut(im_test, 2)
    recolored = recoloriage_MedianCut(im_test, 2)
    recolored_pixels = list(recolored.getdata())
    assert all(p in palette for p in recolored_pixels)  # Tous les pixels de l'image recoloriée doivent appartenir à la palette

test_median_cut_profondeur_0(im_test)
test_median_cut_profondeur_2(im_test)
test_palette_approximation(im_test)
test_recoloriage_taille_identique(im_test)
test_recoloriage_couleurs_dans_palette(im_test)
print("Tous les tests de Median Cut sont validés !")

Tous les tests de Median Cut sont validés !

# Crée un noeud vide à un niveau donné dans l'Octree
def creation_noeud(niveau):
    """Crée un noeud vide pour l'Octree à un niveau spécifié.

    Paramètres:
        niveau (int): Le niveau du noeud dans l'Octree (0 pour la racine, 8 pour les feuilles).

    Retour:
        dict: Un dictionnaire représentant le noeud avec les clés suivantes :
            'somme_couleur' : Somme des composantes de couleur (R, G, B).
            'nb_pixels' (int): Nombre de pixels agrégés dans ce noeud.
            'enfants' (list): Liste de 8 sous-noeuds (initialisés à None).
            'niveau' (int): Niveau du noeud dans l'arbre.
            'est_feuille' (bool): Indique si le noeud est une feuille.
            'parent' (dict): Référence au noeud parent.
    """
    return {
        'somme_couleur': np.zeros(3, dtype=np.float64),  # Somme des couleurs (R, G, B)
        'nb_pixels': 0,                                   # Nombre de pixels agrégés
        'enfants': [None] * 8,                            # 8 sous-noeuds pour un Octree
        'niveau': niveau,                                 # Profondeur actuelle dans l’arbre
        'est_feuille': True,                              # Booléen : le noeud est-il terminal ?
        'parent': None                                    # Référence au parent (utile pour fusionner)
    }

# Détermine quel enfant utiliser dans l’Octree en fonction de la couleur et du niveau
def index_octree(couleur, niveau):
    """Détermine l'index de l'enfant dans l'Octree pour une couleur donnée et un niveau.

    Paramètres:
        couleur (tuple): Un tuple de trois entiers représentant une couleur (R, G, B).
        niveau (int): Le niveau actuel dans l'Octree.

    Retour:
        int: L'index de l'enfant (0-7) correspondant à la couleur et au niveau.
    """
    decalage = 7 - niveau                           # On déplace les bits vers la droite selon la profondeur
    r = (couleur[0] >> decalage) & 1               # Bit significatif pour le rouge
    g = (couleur[1] >> decalage) & 1               # Bit significatif pour le vert
    b = (couleur[2] >> decalage) & 1               # Bit significatif pour le bleu
    return (r << 2) | (g << 1) | b                 # On combine les 3 bits pour obtenir un index entre 0 et 7

# Ajoute une couleur dans l’arbre Octree
def ajout_couleur(noeud, couleur, niveau, reduceur):
    """Ajoute une couleur à l'Octree.

    Paramètres:
        noeud (dict): Le noeud actuel de l'Octree.
        couleur (numpy.ndarray): Un tableau NumPy représentant la couleur (R, G, B).
        niveau (int): Le niveau actuel dans l'Octree.
        reduceur (list): Une liste de listes contenant les noeuds à chaque niveau pour la réduction.

    Retour:
        None: La fonction modifie l'Octree en place.
    """
    if niveau == 8:  # Cas de base : on est à la feuille
        noeud['somme_couleur'] += couleur         # On ajoute les composantes R, G, B
        noeud['nb_pixels'] += 1                   # On compte le pixel
        return

    index = index_octree(couleur.astype(int), niveau)  # Calcul de l'index du sous-noeud

    if noeud['enfants'][index] is None:  # Si le sous-noeud n’existe pas encore
        enfant = creation_noeud(niveau + 1)      # On crée un nouveau noeud enfant
        enfant['parent'] = noeud                 # On enregistre son parent
        noeud['enfants'][index] = enfant         # On l’insère dans la liste des enfants
        reduceur[niveau + 1].append(enfant)      # On garde une référence pour la réduction
        noeud['est_feuille'] = False             # Ce noeud n’est plus une feuille

    ajout_couleur(noeud['enfants'][index], couleur, niveau + 1, reduceur)  # Appel récursif

# Récupère toutes les feuilles de l’arbre (noeuds sans enfants)
def collecte_feuilles(noeud):
    """Récupère toutes les feuilles (noeuds sans enfants) de l'Octree.

    Paramètres:
        noeud (dict): Le noeud actuel de l'Octree.

    Retour:
        list: Une liste de dictionnaires, où chaque dictionnaire représente une feuille de l'arbre.
    """
    if noeud['est_feuille']:  # Si le noeud est une feuille
        return [noeud]        # On le retourne sous forme de liste
    feuilles = []
    for enfant in noeud['enfants']:  # On visite tous les enfants
        if enfant:
            feuilles.extend(collecte_feuilles(enfant))  # Récursion
    return feuilles

# Fusionne tous les enfants d’un noeud vers ce noeud
def fusion_enfants(noeud):
    """Fusionne les couleurs et compte les pixels de tous les enfants d'un noeud vers ce noeud.

    Paramètres:
        noeud (dict): Le noeud dont les enfants doivent être fusionnés.

    Retour:
        None: La fonction modifie le noeud en place.
    """
    for enfant in noeud['enfants']:
        if enfant:
            noeud['somme_couleur'] += enfant['somme_couleur']  # On agrège les couleurs
            noeud['nb_pixels'] += enfant['nb_pixels']          # On compte tous les pixels
    noeud['enfants'] = [None] * 8                              # On supprime les références aux enfants
    noeud['est_feuille'] = True                                # Ce noeud devient une feuille

# Construit l’Octree à partir d’une liste de pixels
def construction_arbre(pixels):
    """Construit un Octree à partir d'une liste de pixels.

    Paramètres:
        pixels (list): Une liste de tuples représentant les couleurs des pixels (R, G, B).

    Retour:
        tuple: Un tuple contenant :
            - dict: La racine de l'Octree.
            - list: Une liste de listes contenant les noeuds à chaque niveau pour la réduction.
    """
    racine = creation_noeud(0)               # Création de la racine de l’arbre
    reduceur = [[] for _ in range(9)]        # Une liste de noeuds pour chaque niveau (0 à 8)
    for couleur in pixels:
        ajout_couleur(racine, np.array(couleur), 0, reduceur)  # Ajout de chaque pixel dans l’arbre
    return racine, reduceur

# Réduit l’Octree jusqu’à ce qu’il ne reste que k feuilles
def reduction_arbre(racine, reduceur, k):
    """Réduit l'Octree jusqu'à ce qu'il ne reste que k feuilles (couleurs).

    Paramètres:
        racine (dict): La racine de l'Octree.
        reduceur (list): Une liste de listes contenant les noeuds à chaque niveau pour la réduction.
        k (int): Le nombre désiré de couleurs dans la palette finale.

    Retour:
        list: Une liste de dictionnaires représentant les feuilles restantes de l'arbre.
    """
    feuilles = collecte_feuilles(racine)  # Liste initiale des feuilles
    while len(feuilles) > k:              # Tant qu’on a plus de k couleurs
        for niveau in reversed(range(1, 9)):        # On part du bas de l’arbre
            if reduceur[niveau]:                    # Si on a des noeuds à ce niveau
                noeud = reduceur[niveau].pop()      # On en prend un
                if noeud['parent']:                 # Si ce noeud a un parent
                    fusion_enfants(noeud['parent']) # On fusionne ses enfants dans le parent
                    break
        feuilles = collecte_feuilles(racine)        # Mise à jour des feuilles
    return feuilles

# Calcule la palette finale (moyenne de chaque feuille)
def obtenir_palette(feuilles):
    """Calcule la palette de couleurs finale à partir des feuilles de l'Octree.

    Paramètres:
        feuilles (list): Une liste de dictionnaires représentant les feuilles de l'arbre.

    Retour:
        list: Une liste de tuples représentant la palette de couleurs (R, G, B).
    """
    palette = []
    for noeud in feuilles:
        if noeud['nb_pixels'] > 0:
            moyenne = (noeud['somme_couleur'] / noeud['nb_pixels']).astype(int)  # Moyenne R, G, B
            palette.append(tuple(moyenne))  # On transforme le vecteur en tuple
    return palette

# Cherche la couleur la plus proche dans une palette
def couleur_plus_proche(couleur, palette, choix_distance=distance_euclid):
    """Trouve la couleur la plus proche dans une palette donnée, en utilisant une fonction de distance spécifiée.

    Paramètres:
        couleur (tuple): La couleur pour laquelle on cherche la correspondance la plus proche (R, G, B).
        palette (list): Une liste de tuples représentant la palette de couleurs (R, G, B).
        choix_distance (callable, optional): La fonction utilisée pour calculer la distance entre deux couleurs. Par défaut, utilise la distance euclidienne (`distance_euclid`).

    Retour:
        tuple: La couleur de la palette la plus proche de la couleur donnée.
    """
    couleur = np.array(couleur)
    meilleure = None
    distance_min = float('inf')
    for c in palette:
        dist = choix_distance(couleur, np.array(c))  # Distance euclidienne
        if dist < distance_min:
            distance_min = dist
            meilleure = c
    return meilleure

# Applique l’algorithme Octree à une image avec k couleurs
def image_octree(image, k, choix_distance=distance_euclid):
    """Applique l'algorithme Octree pour réduire le nombre de couleurs dans une image à k.

    Paramètres:
        image (PIL.Image.Image): L'image à traiter.
        k (int): Le nombre de couleurs désiré dans l'image réduite.
        choix_distance (function): La fonction de distance à utiliser pour comparer les couleurs. Par défaut, utilise la distance euclidienne (`distance_euclid`).

    Retour:
        tuple: Un tuple contenant :
            - PIL.Image.Image: Une nouvelle image avec le nombre de couleurs réduit.
            - list: La palette de couleurs résultante.
    """
    pixels = list(image.getdata())                     # Liste des pixels de l’image
    racine, reduceur = construction_arbre(pixels)      # Création de l’arbre
    feuilles = reduction_arbre(racine, reduceur, k)    # Réduction jusqu’à k couleurs
    palette = obtenir_palette(feuilles)                # Palette finale
    nouveaux_pixels = [couleur_plus_proche(p, palette, choix_distance) for p in pixels]  # Recolorisation
    nouvelle_image = Image.new("RGB", image.size)      # Nouvelle image
    nouvelle_image.putdata(nouveaux_pixels)            # Insertion des pixels recolorés
    return nouvelle_image, palette

# Affiche la palette sous forme d’une bande d’aperçu
def affiche_palette(palette, taille=20):
    """Affiche une palette de couleurs sous forme de bande horizontale.

    Paramètres:
        palette (list): Une liste de tuples représentant la palette de couleurs (R, G, B).
        taille (int, optional): La hauteur (et la largeur de chaque couleur) de la bande de palette. Par défaut, 20.

    Retour:
        PIL.Image.Image: Une image représentant la palette de couleurs.
    """
    img = Image.new("RGB", (taille * len(palette), taille))  # Image rectangulaire
    for i, couleur in enumerate(palette):                    # Pour chaque couleur
        for x in range(taille):                              # Remplissage du rectangle
            for y in range(taille):
                img.putpixel((i * taille + x, y), couleur)
    return img

# Vérifie que l'image recolorisée a bien la même taille que l'image d'origine
def test_taille_identique(image_test):
    image_reduite, _ = image_octree(image_test, 8)   # On applique l’algorithme avec 8 couleurs
    assert image_reduite.size == image_test.size     # La taille doit rester la même

# Vérifie que la palette contient exactement k couleurs
def test_palette_exacte(image_test, k):
    _, palette = image_octree(image_test, k)         # On applique Octree avec k couleurs
    assert len(palette) <= k                         # La palette ne doit pas dépasser k couleurs

# Vérifie que les couleurs utilisées dans l'image recolorisée sont bien dans la palette
def test_couleurs_dans_palette(image_test, k):
    image_reduite, palette = image_octree(image_test, k)     # Nouvelle image et palette
    pixels = list(image_reduite.getdata())                   # Liste des pixels recolorisés
    for pixel in pixels:
        assert pixel in palette                              # Chaque pixel doit appartenir à la palette

# Vérifie qu'on peut recolorier avec 1 seule couleur (image monochrome)
def test_monochrome(image_test):
    image_reduite, palette = image_octree(image_test, 1)     # Image avec 1 seule couleur
    pixels = list(image_reduite.getdata())
    couleur = pixels[0]                                      # On prend le premier pixel
    for pixel in pixels:
        assert pixel == couleur                              # Tous les pixels doivent être identiques

# Fonction pour lancer tous les tests d’un coup
def tests_octree(image_test):
    test_taille_identique(image_test)              # Test de taille
    test_palette_exacte(image_test, 8)             # Test de longueur de palette
    test_couleurs_dans_palette(image_test, 8)      # Test de cohérence entre image et palette
    test_monochrome(image_test)                    # Test monochrome
    print("Tous les tests Octree sont validés !")


# Charger une image pour faire les tests
tests_octree(im_test)

Tous les tests Octree sont validés !

# cette fonction permet de choisir aléatoirement k couleurs initiales parmi celles présentes dans l'image
def initialisation_centroide(liste_pixels, k):
    """Initialise les centroïdes en sélectionnant aléatoirement k couleurs uniques à partir d'une liste de pixels.

    Paramètres:
        liste_pixels (list): Une liste de tuples, chaque tuple représentant une couleur de pixel (R, G, B).
        k (int): Le nombre de centroïdes à initialiser.

    Retour:
        list: Une liste de tuples, chacun représentant un centroïde initial (R, G, B).
    """
    return [random.choice(liste_pixels) for _ in range(k)]

# cette fonction permet d'affecter à chaque pixel la couleur la plus proche
def assigner_cluster(liste_pixels, centroids, choix_distance=distance_euclid):
    """Assigne chaque pixel à un cluster en fonction de la distance à chaque centroïde.

    Paramètres:
        liste_pixels (list): Une liste de tuples, chaque tuple représentant une couleur de pixel (R, G, B).
        centroids (list): Une liste de tuples, chaque tuple représentant un centroïde (R, G, B).
        choix_distance (callable, optional): La fonction de distance à utiliser. Par défaut, utilise la distance euclidienne (`distance_euclid`).

    Retour:
        list: Une liste de listes. Chaque sous-liste contient les pixels assignés à un centroïde spécifique.
    """
    clusters = [[] for _ in centroids]
    for pixel in liste_pixels:
        distances = [choix_distance(pixel, centroid) for centroid in centroids]
        indice_proche = distances.index(min(distances))
        clusters[indice_proche].append(pixel)
    return clusters

# cette fonction permet de recalculer les centroïdes 
def recalcule_centroids(clusters):
    """Recalcule les centroïdes en calculant la couleur moyenne de chaque cluster.
    Si un cluster est vide, un nouveau centroïde aléatoire est généré pour éviter les erreurs.

    Paramètres:
        clusters (list): Une liste de listes. Chaque sous-liste contient les pixels d'un cluster.

    Retour:
        list: Une liste de tuples, chacun représentant un centroïde recalculé (R, G, B).
    """
    centroids = []
    for cluster in clusters:
        if cluster:
            r = sum(pixel[0] for pixel in cluster) // len(cluster)
            g = sum(pixel[1] for pixel in cluster) // len(cluster)
            b = sum(pixel[2] for pixel in cluster) // len(cluster)
            centroids.append((r, g, b))
        else:
            # Cluster vide = nouveau centroïde aléatoire
            centroids.append((random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
    return centroids

def kmeans(image, k, max_iter=10, choix_distance=distance_euclid):
    """Applique l'algorithme k-means pour réduire le nombre de couleurs dans une image.

    Paramètres:
        image (PIL.Image.Image): L'image à traiter.
        k (int): Le nombre de clusters (et donc de couleurs) à utiliser.
        max_iter (int, optional): Le nombre maximum d'itérations de l'algorithme. Par défaut, 10.
        choix_distance (callable, optional): La fonction de distance à utiliser.
            Par défaut, utilise la distance euclidienne (`distance_euclid`).

    Retour:
        PIL.Image.Image: Une nouvelle image avec un nombre de couleurs réduit.
    """
    W, H = image.size
    pixels = image.load()

    # Liste de tous les pixels de l'image
    liste_pixels = [pixels[x, y] for y in range(H) for x in range(W)]

    # Initialisation des centroïdes : on commence par choisir aléatoirement k couleurs aléatoires
    centroids = initialisation_centroide(liste_pixels, k)

    for _ in range(max_iter): # on répète la boucle jusqu'à un nombre maximum d'itérations max_iter
        clusters = assigner_cluster(liste_pixels, centroids, distance_euclid) # on affecte à chaque pixel la couleur la plus proche
        new_centroids = recalcule_centroids(clusters) # on recalcule les centroïdes
        if new_centroids == centroids:
            break
        centroids = new_centroids

    # Création de la nouvelle image
    new_image = Image.new("RGB", (W, H))
    new_pixels = new_image.load()

    for y in range(H):
        for x in range(W):
            original = pixels[x, y]
            distances = [choix_distance(original, centroid) for centroid in centroids]
            indice_proche = distances.index(min(distances))
            new_pixels[x, y] = centroids[indice_proche]

    return new_image

import random
import numpy as np
from PIL import Image

# Test de l'initialisation des centroïdes
def test_initialisation_centroide():
    # On crée une liste de pixels d'exemple
    liste_pixels = [(255, 0, 0), (0, 255, 0), (0, 0, 255)]
    k = 2
    centroids = initialisation_centroide(liste_pixels, k)

    # On vérifie que le nombre de centroïdes générés est égal à k
    assert len(centroids) == k, f"Erreur : nombre de centroïdes ({len(centroids)}) différent de {k}"

    # On vérifie que les centroïdes sont bien choisis parmi les pixels
    assert all(centroid in liste_pixels for centroid in centroids), "Erreur : un des centroïdes n'est pas dans les pixels initiaux"

# Test de l'affectation des pixels aux clusters
def test_assigner_cluster():
    # Exemple de pixels et de centroïdes
    liste_pixels = [(255, 0, 0), (0, 255, 0), (0, 0, 255), (255, 255, 0)]
    centroids = [(255, 0, 0), (0, 0, 255)]

    clusters = assigner_cluster(liste_pixels, centroids)

    # On vérifie qu'il y a autant de clusters que de centroïdes
    assert len(clusters) == len(centroids), f"Erreur : nombre de clusters ({len(clusters)}) différent du nombre de centroïdes ({len(centroids)})"

    # On vérifie que chaque pixel est affecté à un seul cluster
    for cluster in clusters:
        for pixel in cluster:
            assert pixel in liste_pixels, f"Erreur : le pixel {pixel} n'est pas dans la liste des pixels initiaux"

# Test du recalcul des centroïdes
def test_recalcule_centroids():
    # Exemple de clusters
    clusters = [
        [(255, 0, 0), (255, 0, 0)],
        [(0, 255, 0), (0, 255, 0)],
        [(0, 0, 255), (0, 0, 255)]
    ]

    centroids = recalcule_centroids(clusters)

    # On vérifie que le nombre de centroïdes correspond au nombre de clusters
    assert len(centroids) == len(clusters), f"Erreur : nombre de centroïdes ({len(centroids)}) différent du nombre de clusters ({len(clusters)})"

    # On vérifie que les centroïdes sont des moyennes des pixels du cluster
    for i, cluster in enumerate(clusters):
        expected_centroid = tuple(
            sum(pixel[j] for pixel in cluster) // len(cluster) for j in range(3)
        )
        assert centroids[i] == expected_centroid, f"Erreur : centroid {i} attendu {expected_centroid}, trouvé {centroids[i]}"

# Test de l'algorithme K-means
def test_kmeans():
    # Création d'une image test simple de 4 pixels avec 2 couleurs
    img_data = [(255, 0, 0), (255, 0, 0), (0, 255, 0), (0, 255, 0)]  # 2 couleurs : rouge et vert
    test_image = Image.new("RGB", (2, 2))
    test_image.putdata(img_data)

    # Application de l'algorithme K-means avec 2 couleurs
    k = 2
    new_image = kmeans(test_image, k)

    # Vérification que l'image recolorisée a bien 2 couleurs
    new_pixels = list(new_image.getdata())
    assert len(set(new_pixels)) == 2, "Erreur : L'image recolorisée ne contient pas 2 couleurs distinctes"

# Fonction d'exécution des tests pour K-means
def tests_kmeans(image_test, choix_distance):
    test_initialisation_centroide()  # Test de l'initialisation des centroïdes
    test_assigner_cluster()          # Test de l'affectation des clusters
    test_recalcule_centroids()       # Test du recalcul des centroïdes
    test_kmeans()                    # Test de l'algorithme K-means
    print("Tous les tests K-means sont validés !")

# Appel des tests
tests_kmeans(im_test, distance_euclid)

Tous les tests K-means sont validés !

from PIL import Image, ImageDraw
import cmath
import math

# choix de l'image test et affichage de celle-ci
img = Image.open("rainbow.png").convert("RGB")
W, H = img.size
display(img.resize((W // 2, H // 2)))

# Retourne la plus petite puissance de 2 supérieure ou égale à n
def puissance_suivante_de_deux(n):
    """Retourne la plus petite puissance de 2 supérieure ou égale à n.

    Paramètres:
        n (int): Le nombre pour lequel on cherche la puissance de 2 supérieure.

    Retour:
        int: La plus petite puissance de 2 supérieure ou égale à n.
    """
    return 1 << (n - 1).bit_length()

# Complète une liste avec des zéros pour atteindre une taille cible
def zero_padding(liste, taille_cible):
    """Complète une liste avec des zéros pour atteindre une taille cible.

    Paramètres:
        liste (list): La liste à compléter.
        taille_cible (int): La taille désirée de la liste.

    Retour:
        list: Une nouvelle liste complétée avec des zéros.
    """
    return liste + [0] * (taille_cible - len(liste))

# Transformée de Fourier rapide (FFT) 1D récursive
def fft1d(signal):
    """Calcule la Transformée de Fourier Rapide (FFT) 1D d'un signal.
    Implémentation récursive de l'algorithme de Cooley-Tukey.

    Paramètres:
        signal (list): Une liste de nombres complexes représentant le signal.

    Retour:
        list: La transformée de Fourier du signal, une liste de nombres complexes.
    """
    n = len(signal)
    if n <= 1:
        return signal  # Cas de base : un seul élément
    pair = fft1d(signal[0::2])  # FFT des éléments pairs
    impair = fft1d(signal[1::2])  # FFT des éléments impairs
    T = [cmath.exp(-2j * math.pi * k / n) * impair[k] for k in range(n // 2)]  # Calcul des coefficients
    return [pair[k] + T[k] for k in range(n // 2)] + [pair[k] - T[k] for k in range(n // 2)]  # Résultat combiné

# Transformée de Fourier inverse (IFFT) 1D
def ifft1d(signal):
    """Calcule la Transformée de Fourier Inverse (IFFT) 1D d'un signal.
    Utilise la FFT pour calculer efficacement l'IFFT.

    Paramètres:
        signal (list): Une liste de nombres complexes représentant le signal dans le domaine fréquentiel.

    Retour:
        list: Le signal transformé dans le domaine temporel, une liste de nombres complexes.
    """
    n = len(signal)
    conjugue = [x.conjugate() for x in signal]  # Conjugué complexe du signal
    direct = fft1d(conjugue)  # FFT du conjugué
    return [x.conjugate() / n for x in direct]  # On redivise par n pour normaliser

# FFT 2D : applique la FFT 1D sur les lignes puis sur les colonnes d'une matrice
def fft2d(matrice):
    """Calcule la Transformée de Fourier Rapide (FFT) 2D d'une matrice.
    Applique la FFT 1D d'abord sur les lignes, puis sur les colonnes.  Gère le padding pour les dimensions qui ne sont pas des puissances de 2.

    Paramètres:
        matrice (list): Une liste de listes de nombres complexes représentant la matrice.

    Retour:
        tuple: Un tuple contenant :
            - list: La matrice transformée dans le domaine fréquentiel.
            - int: La hauteur originale de la matrice.
            - int: La largeur originale de la matrice.
    """
    h = len(matrice)  # Hauteur d'origine
    w = len(matrice[0])  # Largeur d'origine
    h_p = puissance_suivante_de_deux(h)  # Hauteur arrondie à la puissance de 2
    w_p = puissance_suivante_de_deux(w)  # Largeur arrondie à la puissance de 2

    # On complète chaque ligne avec des zéros
    matrice_padded = [zero_padding(ligne, w_p) for ligne in matrice]
    # On ajoute des lignes de zéros pour compléter en hauteur
    for _ in range(h_p - h):
        matrice_padded.append([0] * w_p)

    # FFT 1D sur chaque ligne
    lignes_fft = [fft1d(ligne) for ligne in matrice_padded]

    # FFT 1D sur chaque colonne
    colonnes_fft = []
    for col in range(w_p):
        colonne = [lignes_fft[row][col] for row in range(h_p)]
        fft_col = fft1d(colonne)
        for row in range(h_p):
            if col == 0:
                colonnes_fft.append([fft_col[row]])
            else:
                colonnes_fft[row].append(fft_col[row])

    # Retourne la matrice transformée + dimensions originales (utile pour l'IFFT)
    return colonnes_fft, h, w

# IFFT 2D : applique l'IFFT 1D sur les colonnes puis sur les lignes
def ifft2d(matrice, h_orig, w_orig):
    """Calcule la Transformée de Fourier Inverse (IFFT) 2D d'une matrice.
    Applique l'IFFT 1D d'abord sur les colonnes, puis sur les lignes.  Tronque le résultat aux dimensions originales avant le padding.

    Paramètres:
        matrice (list): Une liste de listes de nombres complexes représentant la matrice transformée.
        h_orig (int): La hauteur originale de la matrice.
        w_orig (int): La largeur originale de la matrice.

    Retour:
        list: La matrice transformée dans le domaine spatial, tronquée à ses dimensions originales.
    """
    h = len(matrice)
    w = len(matrice[0])

    # IFFT 1D sur chaque colonne
    temp = []
    for col in range(w):
        colonne = [matrice[row][col] for row in range(h)]
        ifft_col = ifft1d(colonne)
        for row in range(h):
            if col == 0:
                temp.append([ifft_col[row]])
            else:
                temp[row].append(ifft_col[row])

    # IFFT 1D sur chaque ligne
    lignes_ifft = [ifft1d(ligne) for ligne in temp]

    # On retourne uniquement la partie de la matrice correspondant aux dimensions d'origine
    return [ligne[:w_orig] for ligne in lignes_ifft[:h_orig]]

# Calcule l'amplitude (valeur absolue) de chaque élément dans une matrice complexe
def amplitude_matrice(matrice):
    """Calcule l'amplitude (valeur absolue) de chaque élément d'une matrice.

    Paramètres:
        matrice (list): Une liste de listes de nombres complexes représentant la matrice.

    Retour:
        list: Une nouvelle matrice de flottants représentant les amplitudes des éléments de la matrice d'entrée.
    """
    return [[abs(valeur) for valeur in ligne] for ligne in matrice]

# Transforme une matrice 2D en une liste 1D (aplatissement)
def aplatir(matrice):
    """Transforme une matrice 2D en une liste 1D en concaténant les lignes.

    Paramètres:
        matrice (list): Une liste de listes représentant la matrice 2D.

    Retour:
        list: Une liste 1D contenant tous les éléments de la matrice.
    """
    return [val for ligne in matrice for val in ligne]

# Extrait les k indices des valeurs les plus importantes (en amplitude) dans une matrice
def extraire_k_indices_importants(matrice, k):
    """Extrait les k indices des valeurs les plus importantes (en amplitude) dans une matrice.

    Paramètres:
        matrice (list): Une liste de listes de nombres (complexes ou réels) représentant la matrice.
        k (int): Le nombre d'indices à extraire.

    Retour:
        set: Un ensemble de tuples, où chaque tuple représente les coordonnées (ligne, colonne)
             d'un des k éléments les plus importants de la matrice.
    """
    plat = aplatir(matrice)  # On aplatit la matrice
    # On trie les indices des éléments en fonction de leur valeur décroissante
    indices = sorted(range(len(plat)), key=lambda i: plat[i], reverse=True)[:k]
    largeur = len(matrice[0])  # Largeur de la matrice pour retransformer les indices en coordonnées 2D
    # On convertit les indices 1D en coordonnées (ligne, colonne)
    return {(i // largeur, i % largeur) for i in indices}

# Applique la FFT sur une matrice, conserve seulement les k composantes principales, puis reconstruit l'image
def appliquer_fft_et_reconstruire(matrice, k):
    """Applique la FFT 2D à une matrice, conserve les k composantes de plus grande amplitude, et reconstruit une matrice à partir de ces composantes.

    Paramètres:
        matrice (list): Une liste de listes de nombres représentant une image.
        k (int): Le nombre de composantes de plus grande amplitude à conserver.

    Retour:
        list: Une nouvelle matrice représentant l'image reconstruite, avec des valeurs
              normalisées entre 0 et 255.
    """
    fft_resultat, h, w = fft2d(matrice)  # Applique la FFT 2D
    amplitude = amplitude_matrice(fft_resultat)  # Calcule l'amplitude de chaque coefficient
    indices_importants = extraire_k_indices_importants(amplitude, k)  # Récupère les indices les plus importants

    # Initialise une matrice de même taille remplie de zéros complexes
    filtrée = [[0 for _ in range(len(fft_resultat[0]))] for _ in range(len(fft_resultat))]

    # On copie uniquement les coefficients importants dans la matrice filtrée
    for i, j in indices_importants:
        filtrée[i][j] = fft_resultat[i][j]

    # Applique l'IFFT pour reconstruire l'image à partir des composantes sélectionnées
    reconstruction_complexe = ifft2d(filtrée, h, w)

    # Convertit les valeurs reconstruites en entiers (entre 0 et 255)
    return [[min(255, max(0, int(round(abs(val))))) for val in ligne] for ligne in reconstruction_complexe]

# Extrait les k valeurs de pixels les plus fréquentes dans une matrice (pour créer une palette de couleurs)
def extraire_palette_depuis_matrice(matrice, k):
    """Extrait les k valeurs de pixels les plus fréquentes d'une matrice.

    Paramètres:
        matrice (list): Une liste de listes représentant la matrice.
        k (int): Le nombre de valeurs de pixels les plus fréquentes à extraire.

    Retour:
        list: Une liste des k valeurs de pixels les plus fréquentes.
    """
    freq = {}
    for ligne in matrice:
        for val in ligne:
            freq[val] = freq.get(val, 0) + 1  # Compte la fréquence d'apparition de chaque valeur
    return sorted(freq, key=freq.get, reverse=True)[:k]  # Retourne les k valeurs les plus fréquentes

# Recolore chaque pixel en lui assignant la couleur la plus proche (en valeur absolue) dans la palette
def recolorer_image_depuis_palette(matrice, palette):
    """Recolore une matrice en assignant à chaque valeur la valeur la plus proche dans une palette donnée.

    Paramètres:
        matrice (list): Une liste de listes représentant la matrice à recolorer.
        palette (list): Une liste de valeurs représentant la palette de couleurs.

    Retour:
        list: Une nouvelle matrice avec les valeurs remplacées par les couleurs les plus proches de la palette.
    """
    return [[min(palette, key=lambda c: abs(val - c)) for val in ligne] for ligne in matrice]

# Convertit une image PIL en matrices numériques selon le mode choisi : "grayscale", "RGB" ou "YCbCr"
def convertir_image_en_matrices(image, mode="grayscale"):
    """Convertit une image PIL en matrices numériques selon le mode de couleur spécifié.

    Paramètres:
        image (PIL.Image.Image): L'image à convertir.
        mode (str): Le mode de conversion de couleur. Les valeurs possibles sont :
            - "grayscale" : conversion en niveaux de gris (une matrice 2D).
            - "RGB"       : conversion en espace de couleur RGB (trois matrices 2D pour R, G, B).
            - "YCbCr"     : conversion en espace de couleur YCbCr (trois matrices 2D pour Y, Cb, Cr).
            Par défaut, "grayscale".

    Retour:
        list ou tuple:
            - Si mode est "grayscale", retourne une matrice 2D où chaque élément est un niveau de gris.
            - Si mode est "RGB" ou "YCbCr", retourne un tuple de trois matrices 2D (R, G, B) ou (Y, Cb, Cr).
    """
    px = image.load()  # Accès direct aux pixels de l'image
    w, h = image.size  # Récupération de la largeur et de la hauteur de l'image

    # Mode niveaux de gris : retourne une matrice 2D des niveaux de gris
    if mode == "grayscale":
        return [[px[x, y] for x in range(w)] for y in range(h)]

    # Mode couleur RGB : retourne 3 matrices séparées pour les canaux R, G et B
    elif mode == "RGB":
        R, G, B = [], [], []
        for y in range(h):
            ligne_R, ligne_G, ligne_B = [], [], []
            for x in range(w):
                r, g, b = px[x, y]  # Extraction des composantes rouge, vert, bleu
                ligne_R.append(r)
                ligne_G.append(g)
                ligne_B.append(b)
            R.append(ligne_R)
            G.append(ligne_G)
            B.append(ligne_B)
        return R, G, B

    # Mode YCbCr : retourne 3 matrices séparées pour les composantes Y (luminance), Cb et Cr (chrominance)
    elif mode == "YCbCr":
        image_ycc = image.convert("YCbCr")  # Conversion de l'image en espace YCbCr
        px = image_ycc.load()  # Chargement des pixels convertis
        Y, Cb, Cr = [], [], []
        for y in range(h):
            ligne_Y, ligne_Cb, ligne_Cr = [], [], []
            for x in range(w):
                y_, cb, cr = px[x, y]  # Extraction des composantes Y, Cb, Cr
                ligne_Y.append(y_)
                ligne_Cb.append(cb)
                ligne_Cr.append(cr)
            Y.append(ligne_Y)
            Cb.append(ligne_Cb)
            Cr.append(ligne_Cr)
        return Y, Cb, Cr

# Reconstruit une image en niveaux de gris ("L") à partir d'une matrice 2D
def reconstruire_image_grayscale(matrice):
    """Reconstruit une image PIL en niveaux de gris à partir d'une matrice 2D.

    Paramètres:
        matrice (list): Une matrice 2D où chaque élément représente un niveau de gris (0-255).

    Retour:
        PIL.Image.Image: Une image en niveaux de gris reconstruite à partir de la matrice.
    """
    h = len(matrice)         # Hauteur de l'image
    w = len(matrice[0])      # Largeur de l'image
    img = Image.new("L", (w, h))  # Création d'une image en mode "L" (luminance, 8 bits)
    px = img.load()          # Accès direct aux pixels de l'image
    for y in range(h):
        for x in range(w):
            px[x, y] = matrice[y][x]  # Attribution de la valeur de gris au pixel (x, y)
    return img

# Reconstruit une image RGB à partir de 3 matrices séparées : R, G et B
def reconstruire_image_depuis_RGB(R, G, B):
    """Reconstruit une image PIL en couleurs RGB à partir de trois matrices 2D représentant les canaux de couleur.

    Paramètres:
        R (list): Une matrice 2D représentant le canal rouge.
        G (list): Une matrice 2D représentant le canal vert.
        B (list): Une matrice 2D représentant le canal bleu.
            Toutes les matrices doivent avoir les mêmes dimensions.

    Retour:
        PIL.Image.Image: Une image RGB reconstruite à partir des matrices de canaux de couleur.
    """
    h = len(R)               # Hauteur de l'image (même pour G et B)
    w = len(R[0])            # Largeur de l'image
    img = Image.new("RGB", (w, h))  # Création d'une image en mode "RGB"
    px = img.load()
    for y in range(h):
        for x in range(w):
            # On recompose le pixel à partir des 3 canaux
            px[x, y] = (R[y][x], G[y][x], B[y][x])
    return img

# Reconstruit une image RGB à partir de matrices Y, Cb et Cr
def reconstruire_image_YCbCr(Y, Cb, Cr):
    """Reconstruit une image PIL en couleurs RGB à partir de matrices 2D YCbCr.

    Paramètres:
        Y (list): Une matrice 2D représentant le canal de luminance (Y).
        Cb (list): Une matrice 2D représentant le canal de chrominance bleue (Cb).
        Cr (list): Une matrice 2D représentant le canal de chrominance rouge (Cr).
            Toutes les matrices doivent avoir les mêmes dimensions.

    Retour:
        PIL.Image.Image: Une image RGB reconstruite à partir des matrices YCbCr.
    """
    h = len(Y)               # Hauteur
    w = len(Y[0])            # Largeur
    img = Image.new("YCbCr", (w, h))  # Création d'une image en mode YCbCr
    px = img.load()
    for y in range(h):
        for x in range(w):
            # Attribution des composantes Y, Cb, Cr au pixel
            px[x, y] = (Y[y][x], Cb[y][x], Cr[y][x])
    return img.convert("RGB")  # Conversion finale en RGB pour affichage standard

# Applique un traitement de compression + recolorisation sur une image
# en utilisant la FFT et une palette réduite de k couleurs
def traitement_image_par_mode(image, mode="grayscale", k=6):
    """Applique un traitement de compression et de recolorisation à une image en utilisant la FFT et une palette de couleurs réduite.
    La fonction prend une image en entrée, la convertit selon le mode de couleur spécifié, applique la Transformée de Fourier Rapide (FFT) pour la compression, extrait une palette de couleurs réduite, recolorie l'image avec cette palette, et retourne l'image résultante ainsi que la palette utilisée.

    Paramètres:
        image (PIL.Image.Image): L'image à traiter.
        mode (str): Le mode de couleur à utiliser pour le traitement. Les valeurs possibles sont :
            - "grayscale": Traite l'image en niveaux de gris.
            - "RGB": Traite l'image en utilisant les canaux rouge, vert et bleu.
            - "YCbCr": Traite l'image en utilisant les canaux luminance (Y) et chrominance (Cb, Cr).
            Par défaut, "grayscale".
        k (int): Le nombre de couleurs à inclure dans la palette réduite. Par défaut, 6.

    Retour:
        tuple: Un tuple contenant deux éléments :
            - PIL.Image.Image: L'image traitée (compressée et recoloriée).
            - list: La palette de couleurs utilisée pour la recoloration. La structure de la palette dépend du mode :
                - Pour "grayscale", c'est une liste de niveaux de gris.
                - Pour "RGB" et "YCbCr", c'est une liste concaténée des palettes de chaque canal (R, G, B ou Y, Cb, Cr).
    """
    img = image.convert("RGB")  # Assure que l'image est bien au format RGB

    # --- Mode niveau de gris ---
    if mode == "grayscale":
        img_L = img.convert("L")  # Convertit l'image RGB en niveaux de gris
        matrice = convertir_image_en_matrices(img_L, mode="grayscale")  # Convertit en matrice 2D
        fft = appliquer_fft_et_reconstruire(matrice, k)  # Applique FFT et garde les k composantes principales
        palette = extraire_palette_depuis_matrice(fft, k)  # Récupère les k couleurs les plus fréquentes
        recoloree = recolorer_image_depuis_palette(matrice, palette)  # Recolore l'image avec la palette
        return reconstruire_image_grayscale(recoloree), palette  # Reconstruit l'image finale + palette utilisée

    # --- Mode RGB (3 canaux séparés) ---
    elif mode == "RGB":
        R, G, B = convertir_image_en_matrices(img, mode="RGB")  # Décompose l'image en 3 matrices R, G, B

        # Applique FFT + reconstruction sur chaque canal
        R_fft = appliquer_fft_et_reconstruire(R, k)
        G_fft = appliquer_fft_et_reconstruire(G, k)
        B_fft = appliquer_fft_et_reconstruire(B, k)

        # Extrait les palettes dominantes de chaque canal
        palette_R = extraire_palette_depuis_matrice(R_fft, k)
        palette_G = extraire_palette_depuis_matrice(G_fft, k)
        palette_B = extraire_palette_depuis_matrice(B_fft, k)

        # Recolore chaque canal selon sa palette
        R_recolore = recolorer_image_depuis_palette(R, palette_R)
        G_recolore = recolorer_image_depuis_palette(G, palette_G)
        B_recolore = recolorer_image_depuis_palette(B, palette_B)

        # Concatène les 3 palettes pour référence
        palette = palette_R + palette_G + palette_B

        # Reconstruit l'image RGB recolorisée
        return reconstruire_image_depuis_RGB(R_recolore, G_recolore, B_recolore), palette

    # --- Mode YCbCr (utilisé pour la compression) ---
    elif mode == "YCbCr":
        Y, Cb, Cr = convertir_image_en_matrices(img, mode="YCbCr")  # Décomposition Y, Cb, Cr

        # Applique FFT + reconstruction
        Y_fft = appliquer_fft_et_reconstruire(Y, k)
        Cb_fft = appliquer_fft_et_reconstruire(Cb, k)
        Cr_fft = appliquer_fft_et_reconstruire(Cr, k)

        # Extrait les palettes dominantes
        palette_Y = extraire_palette_depuis_matrice(Y_fft, k)
        palette_Cb = extraire_palette_depuis_matrice(Cb_fft, k)
        palette_Cr = extraire_palette_depuis_matrice(Cr_fft, k)

        # Recolore chaque canal selon sa palette
        Y_recolore = recolorer_image_depuis_palette(Y, palette_Y)
        Cb_recolore = recolorer_image_depuis_palette(Cb, palette_Cb)
        Cr_recolore = recolorer_image_depuis_palette(Cr, palette_Cr)

        # Concatène les 3 palettes
        palette = palette_Y + palette_Cb + palette_Cr

        # Reconstruit une image RGB à partir des données YCbCr recolorées
        return reconstruire_image_YCbCr(Y_recolore, Cb_recolore, Cr_recolore), palette

image_recoloriee, palette_utilisee = traitement_image_par_mode(img, mode="grayscale", k=10)
display(image_recoloriee)
print(len(palette_utilisee))

10

image_recoloriee, palette_utilisee = traitement_image_par_mode(img, mode="YCbCr", k=32)
display(image_recoloriee)
print(len(palette_utilisee)//3)

32

image_recoloriee, palette_utilisee = traitement_image_par_mode(img, mode="RGB", k=32)
display(image_recoloriee)
print(len(palette_utilisee)//3)

32

def conversion_gris(image):
    """Convertit une image couleur en niveaux de gris.

    Paramètres :
        image : PIL.Image.Image
            L'image à convertir.

    Retour :
        PIL.Image.Image
            Une nouvelle image en niveaux de gris.
    """
    px = image.load()
    W, H = image.size
    for x in range(0, W):
        for y in range(0, H):
            m = int(0.30*px[x, y][0] + 0.59*px[x, y][1] + 0.11*px[x, y][2])
            px[x, y] = (m, m, m)
    return image

degrade = Image.open("rainbow.png").convert("RGB")
result = conversion_gris(degrade)
display(result.resize((W//2, H//2)))

# On définit le noyau de flou gaussien 3x3
gauss3 = [[1,2,1],
          [2,4,2],
          [1,2,1]]

# On définit un deuxième noyau de flou gaussien :

gauss7 = [[1,1,2,2,2,1,1],
          [1,2,2,4,2,2,1],
          [2,2,4,8,4,2,2],
          [2,4,8,16,8,4,2],
          [2,2,4,8,4,2,2],
          [1,2,2,4,2,2,1],
          [1,1,2,2,2,1,1]]

def somme_matrice(m: list = []) -> float:
    somme = 0
    for i in m:
        for j in i:
            somme += j
    return somme

assert somme_matrice(gauss3) == 16
assert somme_matrice(gauss7) == 140

def convolution(image, m: list) -> None:
    """Applique une opération de convolution à une image.

    Paramètres :
        image : PIL.Image.Image
            L'image sur laquelle appliquer la convolution.
        m : list[list[int]]
            Le masque de convolution (noyau). Doit être une matrice carrée ou rectangulaire.

    Retour :
        PIL.Image.Image
            Une nouvelle image résultant de l'opération de convolution.
    """
    w = len(m)
    h = len(m[0])
    wp = int((w - 1) / 2)
    hp = int((h - 1) / 2)
    W, H = image.size

    somme_m = somme_matrice(m)

    imflou = image.copy()
    pxflou = imflou.load()

    px = image.load()
    pixels_copy = [[px[x, y] for y in range(H)] for x in range(W)]

    for x in range(wp, W - wp):
        for y in range(hp, H - hp):
            r_sum = g_sum = b_sum = 0
            for a in range(-wp, wp + 1):
                for b in range(-hp, hp + 1):
                    r, g, b_ = pixels_copy[x + a][y + b]
                    coeff = m[a + wp][b + hp]
                    r_sum += r * coeff
                    g_sum += g * coeff
                    b_sum += b_ * coeff
            r = int(r_sum / somme_m)
            g = int(g_sum / somme_m)
            b = int(b_sum / somme_m)
            pxflou[x, y] = (r, g, b)

    return imflou

# On ouvre l'image de test
image_test_flou = Image.open("test_flou_gaussien.png").convert("RGB")
# On applique le flou gaussien
im_flou = convolution(image_test_flou, gauss3)
im_flou_2 = convolution(image_test_flou, gauss7)

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(image_test_flou)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(im_flou)
axs[1].set_title("Image avec flou gaussien : noyau 3x3")
axs[1].axis('off')

axs[2].imshow(im_flou_2)
axs[2].set_title("Image avec flou gaussien : noyau 7x7")
axs[2].axis('off')

plt.tight_layout()
plt.show()

from PIL import Image, ImageFile, ImageDraw, ImageChops, ImageFilter
im_pil = image_test_flou.filter(ImageFilter.GaussianBlur)

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(im_flou)
axs[0].set_title("Image avec flou gaussien : noyau 3x3")
axs[0].axis('off')

axs[1].imshow(im_flou_2)
axs[1].set_title("Image avec flou gaussien : noyau 7x7")
axs[1].axis('off')

axs[2].imshow(im_pil)
axs[2].set_title("Image avec flou gaussien de PIL")
axs[2].axis('off')

plt.tight_layout()
plt.show()

# Définition des noyaux sobel
sobely3 = [[-1, 0, 1],
           [-2, 0, 2],
           [-1, 0, 1]]

sobelx3 = [[-1, -2, -1],
           [0, 0, 0],
           [1, 2, 1]]

# On réalise la détection de contour de l'image dans le sens des X ou Y avec la fonction de convolution Sobel
def convolution_sobel(image, m: list, f=1):
    """Applique un filtre de Sobel à une image pour détecter les contours.

    Paramètres :
        image : PIL.Image.Image
            L'image sur laquelle appliquer le filtre de Sobel.
        m : list[list[int]]
            Le masque de convolution de Sobel (noyau).  Doit être une matrice carrée ou rectangulaire.
        f : int, optionnel
            Facteur multiplicatif appliqué au résultat de la convolution. Par défaut, 1.

    Retour :
        PIL.Image.Image
            Une nouvelle image en niveaux de gris représentant les contours détectés.
            Les valeurs de pixels sont normalisées entre 0 et 255.
    """
    # Convertir l'image en niveaux de gris si ce n'est pas déjà le cas
    image = image.convert("L")
    px = image.load()
    W, H = image.size
    w = len(m)
    h = len(m[0])
    wp = int((w - 1) / 2)
    hp = int((h - 1) / 2)

    # Création d'une nouvelle image vide
    new_image = Image.new("L", image.size)
    new_px = new_image.load()

    min_val = float('inf')
    max_val = float('-inf')
    result = [[0 for _ in range(H)] for _ in range(W)]

    # Appliquer la convolution et stocker les résultats bruts
    for x in range(wp, W - wp):
        for y in range(hp, H - hp):
            sum = 0
            for a in range(-wp, wp + 1):
                for b in range(-hp, hp + 1):
                    sum += px[x + a, y + b] * m[a + wp][b + hp]

            result[x][y] = sum
            min_val = min(min_val, sum)
            max_val = max(max_val, sum)

    # Normalisation des valeurs dans [0, 255]
    for x in range(W):
        for y in range(H):
            val = result[x][y]
            norm_val = int(255 * (val - min_val) / (max_val - min_val)) if max_val != min_val else 0
            new_px[x, y] = norm_val

    return new_image

image_test_flou = Image.open("test_flou_gaussien.png").convert("RGB")

# On la convertit en niveau de gris
image_test_flou = conversion_gris(image_test_flou)

# Appliquer la convolution Sobel avec les noyaux
test_conv_y = convolution_sobel(image_test_flou, sobely3, f=1)
test_conv_x = convolution_sobel(image_test_flou, sobelx3, f=1)

# Affichage des images
fig, axs = plt.subplots(1, 3, figsize=(15, 5))

# Affichage de l'image originale
axs[0].imshow(image_test_flou)
axs[0].set_title("Image originale en nuances de gris")
axs[0].axis('off')

# Affichage de l'image après détection de contours dans le sens des X
axs[1].imshow(test_conv_x, cmap='gray')
axs[1].set_title("Détection de contour dans le sens des X")
axs[1].axis('off')

# Affichage de l'image après détection de contours dans le sens des Y
axs[2].imshow(test_conv_y, cmap='gray')
axs[2].set_title("Détection de contour dans le sens des Y")
axs[2].axis('off')

plt.tight_layout()
plt.show()

# Calcul de la magnitude du gradient
def magnitude_gradient(gx_img, gy_img):
    """Calcule la magnitude du gradient à partir des composantes X et Y du gradient.

    Paramètres :
        gx_img : PIL.Image.Image
            L'image représentant la composante du gradient en X.
        gy_img : PIL.Image.Image
            L'image représentant la composante du gradient en Y.

    Retour :
        PIL.Image.Image
            Une nouvelle image en niveaux de gris représentant la magnitude du gradient.
            Les valeurs de pixels sont normalisées entre 0 et 255.
    """
    W, H = gx_img.size
    px_gx = gx_img.load()
    px_gy = gy_img.load()

    # Tableau pour stocker les magnitudes
    magnitude = [[0 for _ in range(H)] for _ in range(W)]
    max_val = 0

    # Calcul des magnitudes et récupération du maximum
    for x in range(W):
        for y in range(H):
            mag = math.sqrt(px_gx[x, y]**2 + px_gy[x, y]**2)
            magnitude[x][y] = mag
            max_val = max(max_val, mag)

    # Création de l'image de sortie
    new_image = Image.new("L", (W, H))
    new_px = new_image.load()

    for x in range(W):
        for y in range(H):
            norm = int(255 * magnitude[x][y] / max_val) if max_val != 0 else 0
            new_px[x, y] = norm

    return new_image

# Seuil binaire
def seuillage(image, seuil=100):
    """Applique un seuillage binaire à une image en niveaux de gris.

    Paramètres :
        image : PIL.Image.Image
            L'image à seuiller.
        seuil : int, optionnel
            La valeur de seuil. Les pixels avec une valeur supérieure au seuil
            deviennent blancs (255), les autres deviennent noirs (0). Par défaut, 100.

    Retour :
        PIL.Image.Image
            Une nouvelle image binaire (niveaux de gris 0 ou 255).
    """
    image = image.copy()
    px = image.load()
    W, H = image.size
    for x in range(W):
        for y in range(H):
            if px[x, y] > seuil:
                px[x, y] = 255
            else :
                px[x, y] = 0
    return image

img = Image.open("test_flou_gaussien.png")
gx = convolution_sobel(img, sobelx3)
gy = convolution_sobel(img, sobely3)
mag = magnitude_gradient(gx, gy)
mag_thresh = seuillage(mag, seuil=142) # Attention à ne pas choisir un seuil trop élevé ni trop faible

fig, axs = plt.subplots(1, 5, figsize=(20, 5))

images = [img.convert("L"), gx, gy, mag, mag_thresh]
titles = ["Image originale (niveaux de gris)", "Sobel X", "Sobel Y", "Magnitude", "Contours (avec seuil)"]

for ax, im, title in zip(axs, images, titles):
    ax.imshow(im, cmap='gray')
    ax.set_title(title)
    ax.axis("off")

plt.tight_layout()
plt.show()

def score_synthese(image_originale, img1, img2, img3, img4, img5, img6, algos, choix_distance=distance_euclid):

    # Liste des images recoloriées
    images_recolorees = [img1, img2, img3, img4, img5, img6]

    # On récupère les élements de l'image
    largeur, hauteur = image_originale.size
    pixels_orig = image_originale.load()

    # Distance maximale possible entre deux couleurs RGB (du noir au blanc)
    distance_max = choix_distance((0, 0, 0), (255, 255, 255))
    erreurs_totale = []
    erreurs_moyenne = []
    pourcentages_erreur = []

    for k in range(len(images_recolorees)):
        image_recoloriee = images_recolorees[k]
        pixels_reco = image_recoloriee.load()

        erreur_totale = 0
        for i in range(largeur):
            for j in range(hauteur):
                couleur1 = pixels_orig[i, j]         # pixel original
                couleur2 = pixels_reco[i, j]         # pixel recolorié
                erreur_totale += choix_distance(couleur1, couleur2)

        erreurs_totale.append(erreur_totale)
        erreur_moyenne = erreur_totale / (largeur * hauteur)
        erreurs_moyenne.append(erreur_moyenne)
        pourcentage_erreur = (erreur_moyenne / distance_max) * 100
        pourcentages_erreur.append(pourcentage_erreur)

        print(f"------ {algos[k]} ------")
        print(f"erreur_totale : {round(erreur_totale, 2)}")
        print(f"erreur_moyenne : {round(erreur_moyenne, 2)}")
        print(f"pourcentage_erreur : {round(pourcentage_erreur, 2)}")

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = distance_euclid
img_lovelace = Image.open("lovelace.png").convert("RGB")

img_lovelace_euclid_median_cut = recoloriage_MedianCut(img_lovelace, n, choix_distance)
img_lovelace_euclid_octree, pallette_octree = image_octree(img_lovelace, k, choix_distance)
img_lovelace_euclid_k_means = kmeans(img_lovelace, k, nb_iter, choix_distance)

img_lovelace_euclid_methode_naive, palette_naive = methode_naive(img_lovelace, choix_distance,k)
img_lovelace_euclid_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_lovelace, mode="YCbCr", k=k)
img_lovelace_euclid_fourier_RGB, palette_RGB = traitement_image_par_mode(img_lovelace, mode="RGB", k=k)

images_lovelace_euclid = [img_lovelace.convert("RGB"), img_lovelace_euclid_median_cut, img_lovelace_euclid_octree, img_lovelace_euclid_k_means,
          img_lovelace_euclid_methode_naive, img_lovelace_euclid_fourier_YCbCr, img_lovelace_euclid_fourier_RGB]

#images = [img.convert("RGB"), img.convert("RGB"), img.convert("RGB"), img.convert("RGB"),
#          img.convert("RGB"), img.convert("RGB"), img.convert("RGB")]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_lovelace_euclid)):
    axs[i].imshow(images_lovelace_euclid[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_lovelace_euclid_median_cut = difference(img_lovelace, img_lovelace_euclid_median_cut, choix_distance)
diff_lovelace_euclid_octree = difference(img_lovelace, img_lovelace_euclid_octree, choix_distance)
diff_lovelace_euclid_k_means = difference(img_lovelace, img_lovelace_euclid_k_means, choix_distance)

diff_lovelace_euclid_methode_naive = difference(img_lovelace, img_lovelace_euclid_methode_naive, choix_distance)
diff_lovelace_euclid_fourier_YCbCr = difference(img_lovelace, img_lovelace_euclid_fourier_YCbCr, choix_distance)
diff_lovelace_euclid_fourier_RGB = difference(img_lovelace, img_lovelace_euclid_fourier_RGB, choix_distance)

images_diff_lovelace_euclid = [diff_lovelace_euclid_median_cut, diff_lovelace_euclid_octree, diff_lovelace_euclid_k_means,
          diff_lovelace_euclid_methode_naive, diff_lovelace_euclid_fourier_YCbCr, diff_lovelace_euclid_fourier_RGB]

#images = [img.convert("RGB"), img.convert("RGB"), img.convert("RGB"), img.convert("RGB"),
#          img.convert("RGB"), img.convert("RGB"), img.convert("RGB")]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_diff_lovelace_euclid)):
    axs[i].imshow(images_diff_lovelace_euclid[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_lovelace, img_lovelace_euclid_median_cut, img_lovelace_euclid_octree, img_lovelace_euclid_k_means, img_lovelace_euclid_methode_naive, img_lovelace_euclid_fourier_YCbCr, img_lovelace_euclid_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_euclid)

------ Median Cut ------
erreur_totale : 532600.28
erreur_moyenne : 15.63
pourcentage_erreur : 3.54
------ Octree ------
erreur_totale : 1000653.76
erreur_moyenne : 29.36
pourcentage_erreur : 6.65
------ Kmeans ------
erreur_totale : 583754.3
erreur_moyenne : 17.13
pourcentage_erreur : 3.88
------ Naive ------
erreur_totale : 4144815.53
erreur_moyenne : 121.62
pourcentage_erreur : 27.54
------ YCbCr ------
erreur_totale : 4574439.66
erreur_moyenne : 134.23
pourcentage_erreur : 30.39
------ RGB ------
erreur_totale : 4225203.35
erreur_moyenne : 123.98
pourcentage_erreur : 28.07

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = distance_lab
img_lovelace = Image.open("lovelace.png").convert("RGB")

img_lovelace_76_median_cut = recoloriage_MedianCut(img_lovelace, n, choix_distance)
img_lovelace_76_octree, pallette_octree = image_octree(img_lovelace, k, choix_distance)
img_lovelace_76_k_means = kmeans(img_lovelace, k, nb_iter, choix_distance)

img_lovelace_76_methode_naive, palette_naive_lovelace_76_ = methode_naive(img_lovelace, choix_distance,k)
img_lovelace_76_fourier_YCbCr, palette_lovelace_76_YCbCr = traitement_image_par_mode(img_lovelace, mode="YCbCr", k=k)
img_lovelace_76_fourier_RGB, palette_lovelace_76_RGB = traitement_image_par_mode(img_lovelace, mode="RGB", k=k)

images_lovelace_76 = [img_lovelace.convert("RGB"), img_lovelace_76_median_cut, img_lovelace_76_octree, img_lovelace_76_k_means,
          img_lovelace_76_methode_naive, img_lovelace_76_fourier_YCbCr, img_lovelace_76_fourier_RGB]

#images = [img.convert("RGB"), img.convert("RGB"), img.convert("RGB"), img.convert("RGB"),
#          img.convert("RGB"), img.convert("RGB"), img.convert("RGB")]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_lovelace_76)):
    axs[i].imshow(images_lovelace_76[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_lovelace_e76_median_cut = difference(img_lovelace, img_lovelace_76_median_cut, choix_distance)
diff_lovelace_e76_octree = difference(img_lovelace, img_lovelace_76_octree, choix_distance)
diff_lovelace_e76_k_means = difference(img_lovelace, img_lovelace_76_k_means, choix_distance)

diff_lovelace_e76_methode_naive = difference(img_lovelace, img_lovelace_76_methode_naive, choix_distance)
diff_lovelace_e76_fourier_YCbCr = difference(img_lovelace, img_lovelace_76_fourier_YCbCr, choix_distance)
diff_lovelace_e76_fourier_RGB = difference(img_lovelace, img_lovelace_76_fourier_RGB, choix_distance)

diff_lovelace_76 = [diff_lovelace_e76_median_cut, diff_lovelace_e76_octree, diff_lovelace_e76_k_means,
          diff_lovelace_e76_methode_naive, diff_lovelace_e76_fourier_YCbCr, diff_lovelace_e76_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_lovelace_76)):
    axs[i].imshow(diff_lovelace_76[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_lovelace, img_lovelace_76_median_cut, img_lovelace_76_octree, img_lovelace_76_k_means, img_lovelace_76_methode_naive, img_lovelace_76_fourier_YCbCr, img_lovelace_76_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_lab)

------ Median Cut ------
erreur_totale : 201561.93
erreur_moyenne : 5.91
pourcentage_erreur : 5.91
------ Octree ------
erreur_totale : 280607.04
erreur_moyenne : 8.23
pourcentage_erreur : 8.23
------ Kmeans ------
erreur_totale : 200170.4
erreur_moyenne : 5.87
pourcentage_erreur : 5.87
------ Naive ------
erreur_totale : 993195.31
erreur_moyenne : 29.14
pourcentage_erreur : 29.14
------ YCbCr ------
erreur_totale : 1075312.79
erreur_moyenne : 31.55
pourcentage_erreur : 31.55
------ RGB ------
erreur_totale : 1057038.61
erreur_moyenne : 31.02
pourcentage_erreur : 31.02

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_lovelace = Image.open("lovelace.png").convert("RGB")

img_lovelace_2000_median_cut = recoloriage_MedianCut(img_lovelace, n, choix_distance)
img_lovelace_2000_octree, pallette_octree = image_octree(img_lovelace, k, choix_distance)
img_lovelace_2000_k_means = kmeans(img_lovelace, k, nb_iter, choix_distance)

img_lovelace_2000_methode_naive, palette_naive_lovelace_76_ = methode_naive(img_lovelace, choix_distance,k)
img_lovelace_2000_fourier_YCbCr, palette_lovelace_76_YCbCr = traitement_image_par_mode(img_lovelace, mode="YCbCr", k=k)
img_lovelace_2000_fourier_RGB, palette_lovelace_76_RGB = traitement_image_par_mode(img_lovelace, mode="RGB", k=k)

images_lovelace_2000 = [img_lovelace.convert("RGB"), img_lovelace_2000_median_cut, img_lovelace_2000_octree, img_lovelace_2000_k_means,
          img_lovelace_2000_methode_naive, img_lovelace_2000_fourier_YCbCr, img_lovelace_2000_fourier_RGB]

#images = [img.convert("RGB"), img.convert("RGB"), img.convert("RGB"), img.convert("RGB"),
#          img.convert("RGB"), img.convert("RGB"), img.convert("RGB")]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_lovelace_2000)):
    axs[i].imshow(images_lovelace_2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_lovelace_2000_median_cut = difference(img_lovelace, img_lovelace_2000_median_cut, choix_distance)
diff_lovelace_2000_octree = difference(img_lovelace, img_lovelace_2000_octree, choix_distance)
diff_lovelace_2000_k_means = difference(img_lovelace, img_lovelace_2000_k_means, choix_distance)

diff_lovelace_2000_methode_naive = difference(img_lovelace, img_lovelace_2000_methode_naive, choix_distance)
diff_lovelace_2000_fourier_YCbCr = difference(img_lovelace, img_lovelace_2000_fourier_YCbCr, choix_distance)
diff_lovelace_2000_fourier_RGB = difference(img_lovelace, img_lovelace_2000_fourier_RGB, choix_distance)

diff_lovelace_2000 = [diff_lovelace_2000_median_cut, diff_lovelace_2000_octree, diff_lovelace_2000_k_means,
          diff_lovelace_2000_methode_naive, diff_lovelace_2000_fourier_YCbCr, diff_lovelace_2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_lovelace_2000)):
    axs[i].imshow(diff_lovelace_2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_lovelace, img_lovelace_2000_median_cut, img_lovelace_2000_octree, img_lovelace_2000_k_means, img_lovelace_2000_methode_naive, img_lovelace_2000_fourier_YCbCr, img_lovelace_2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 172743.97
erreur_moyenne : 5.07
pourcentage_erreur : 5.07
------ Octree ------
erreur_totale : 221488.08
erreur_moyenne : 6.5
pourcentage_erreur : 6.5
------ Kmeans ------
erreur_totale : 167045.67
erreur_moyenne : 4.9
pourcentage_erreur : 4.9
------ Naive ------
erreur_totale : 909651.22
erreur_moyenne : 26.69
pourcentage_erreur : 26.69
------ YCbCr ------
erreur_totale : 994747.29
erreur_moyenne : 29.19
pourcentage_erreur : 29.19
------ RGB ------
erreur_totale : 976168.49
erreur_moyenne : 28.64
pourcentage_erreur : 28.64

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = distance_euclid
img_paysage = Image.open("paysage.png").convert("RGB")

img_paysage_euclid_median_cut = recoloriage_MedianCut(img_paysage, n, choix_distance)
img_paysage_euclid_octree, pallette_octree = image_octree(img_paysage, k, choix_distance)
img_paysage_euclid_k_means = kmeans(img_paysage, k, nb_iter, choix_distance)

img_paysage_euclid_methode_naive, palette_naive = methode_naive(img_paysage, choix_distance,k)
img_paysage_euclid_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_paysage, mode="YCbCr", k=k)
img_paysage_euclid_fourier_RGB, palette_RGB = traitement_image_par_mode(img_paysage, mode="RGB", k=k)

images_paysage_euclid = [img_paysage.convert("RGB"), img_paysage_euclid_median_cut, img_paysage_euclid_octree, img_paysage_euclid_k_means,
          img_paysage_euclid_methode_naive, img_paysage_euclid_fourier_YCbCr, img_paysage_euclid_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_paysage_euclid)):
    axs[i].imshow(images_paysage_euclid[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_paysage_euclid_median_cut = difference(img_paysage, img_paysage_euclid_median_cut, choix_distance)
diff_paysage_euclid_octree = difference(img_paysage, img_paysage_euclid_octree, choix_distance)
diff_paysage_euclid_k_means = difference(img_paysage, img_paysage_euclid_k_means, choix_distance)

diff_paysage_euclid_methode_naive = difference(img_paysage, img_paysage_euclid_methode_naive, choix_distance)
diff_paysage_euclid_fourier_YCbCr = difference(img_paysage, img_paysage_euclid_fourier_YCbCr, choix_distance)
diff_paysage_euclid_fourier_RGB = difference(img_paysage, img_paysage_euclid_fourier_RGB, choix_distance)

diff_paysage_euclid = [diff_paysage_euclid_median_cut, diff_paysage_euclid_octree, diff_paysage_euclid_k_means,
          diff_paysage_euclid_methode_naive, diff_paysage_euclid_fourier_YCbCr, diff_paysage_euclid_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_paysage_euclid)):
    axs[i].imshow(diff_paysage_euclid[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_paysage, img_paysage_euclid_median_cut, img_paysage_euclid_octree, img_paysage_euclid_k_means, img_paysage_euclid_methode_naive, img_paysage_euclid_fourier_YCbCr, img_paysage_euclid_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_euclid)

------ Median Cut ------
erreur_totale : 254866.42
erreur_moyenne : 31.74
pourcentage_erreur : 7.19
------ Octree ------
erreur_totale : 317347.63
erreur_moyenne : 39.52
pourcentage_erreur : 8.95
------ Kmeans ------
erreur_totale : 227844.26
erreur_moyenne : 28.37
pourcentage_erreur : 6.42
------ Naive ------
erreur_totale : 513976.77
erreur_moyenne : 64.01
pourcentage_erreur : 14.49
------ YCbCr ------
erreur_totale : 567166.68
erreur_moyenne : 70.63
pourcentage_erreur : 15.99
------ RGB ------
erreur_totale : 571203.48
erreur_moyenne : 71.13
pourcentage_erreur : 16.11

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = distance_lab
img_paysage = Image.open("paysage.png").convert("RGB")

img_paysage_e76_median_cut = recoloriage_MedianCut(img_paysage, n, choix_distance)
img_paysage_e76_octree, pallette_octree = image_octree(img_paysage, k, choix_distance)
img_paysage_e76_k_means = kmeans(img_paysage, k, nb_iter, choix_distance)

img_paysage_e76_methode_naive, palette_naive = methode_naive(img_paysage, choix_distance,k)
img_paysage_e76_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_paysage, mode="YCbCr", k=k)
img_paysage_e76_fourier_RGB, palette_RGB = traitement_image_par_mode(img_paysage, mode="RGB", k=k)

images_paysage_e76 = [img_paysage.convert("RGB"), img_paysage_e76_median_cut, img_paysage_e76_octree, img_paysage_e76_k_means,
          img_paysage_e76_methode_naive, img_paysage_e76_fourier_YCbCr, img_paysage_e76_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_paysage_e76)):
    axs[i].imshow(images_paysage_e76[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_paysage_e76_median_cut = difference(img_paysage, img_paysage_e76_median_cut, choix_distance)
diff_paysage_e76_octree = difference(img_paysage, img_paysage_e76_octree, choix_distance)
diff_paysage_e76_k_means = difference(img_paysage, img_paysage_e76_k_means, choix_distance)

diff_paysage_e76_methode_naive = difference(img_paysage, img_paysage_e76_methode_naive, choix_distance)
diff_paysage_e76_fourier_YCbCr = difference(img_paysage, img_paysage_e76_fourier_YCbCr, choix_distance)
diff_paysage_e76_fourier_RGB = difference(img_paysage, img_paysage_e76_fourier_RGB, choix_distance)

diff_paysage_e76 = [diff_paysage_e76_median_cut, diff_paysage_e76_octree, diff_paysage_e76_k_means,
          diff_paysage_e76_methode_naive, diff_paysage_e76_fourier_YCbCr, diff_paysage_e76_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_paysage_e76)):
    axs[i].imshow(diff_paysage_e76[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_paysage, img_paysage_e76_median_cut, img_paysage_e76_octree, img_paysage_e76_k_means, img_paysage_e76_methode_naive, img_paysage_e76_fourier_YCbCr, img_paysage_e76_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_lab)

------ Median Cut ------
erreur_totale : 92460.19
erreur_moyenne : 11.51
pourcentage_erreur : 11.51
------ Octree ------
erreur_totale : 113636.41
erreur_moyenne : 14.15
pourcentage_erreur : 14.15
------ Kmeans ------
erreur_totale : 84450.62
erreur_moyenne : 10.52
pourcentage_erreur : 10.52
------ Naive ------
erreur_totale : 179306.22
erreur_moyenne : 22.33
pourcentage_erreur : 22.33
------ YCbCr ------
erreur_totale : 211087.89
erreur_moyenne : 26.29
pourcentage_erreur : 26.29
------ RGB ------
erreur_totale : 236313.85
erreur_moyenne : 29.43
pourcentage_erreur : 29.43

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_paysage = Image.open("paysage.png").convert("RGB")

img_paysage_e2000_median_cut = recoloriage_MedianCut(img_paysage, n, choix_distance)
img_paysage_e2000_octree, pallette_octree = image_octree(img_paysage, k, choix_distance)
img_paysage_e2000_k_means = kmeans(img_paysage, k, nb_iter, choix_distance)

img_paysage_e2000_methode_naive, palette_naive = methode_naive(img_paysage, choix_distance,k)
img_paysage_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_paysage, mode="YCbCr", k=k)
img_paysage_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_paysage, mode="RGB", k=k)

images_paysage_e2000 = [img_paysage.convert("RGB"), img_paysage_e2000_median_cut, img_paysage_e2000_octree, img_paysage_e2000_k_means,
          img_paysage_e2000_methode_naive, img_paysage_e2000_fourier_YCbCr, img_paysage_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_paysage_e2000)):
    axs[i].imshow(images_paysage_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_paysage_e2000_median_cut = difference(img_paysage, img_paysage_e2000_median_cut, choix_distance)
diff_paysage_e2000_octree = difference(img_paysage, img_paysage_e2000_octree, choix_distance)
diff_paysage_e2000_k_means = difference(img_paysage, img_paysage_e2000_k_means, choix_distance)

diff_paysage_e2000_methode_naive = difference(img_paysage, img_paysage_e2000_methode_naive, choix_distance)
diff_paysage_e2000_fourier_YCbCr = difference(img_paysage, img_paysage_e2000_fourier_YCbCr, choix_distance)
diff_paysage_e2000_fourier_RGB = difference(img_paysage, img_paysage_e2000_fourier_RGB, choix_distance)

diff_paysage_e2000 = [diff_paysage_e2000_median_cut, diff_paysage_e2000_octree, diff_paysage_e2000_k_means,
          diff_paysage_e2000_methode_naive, diff_paysage_e2000_fourier_YCbCr, diff_paysage_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_paysage_e2000)):
    axs[i].imshow(diff_paysage_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_paysage, img_paysage_e2000_median_cut, img_paysage_e2000_octree, img_paysage_e2000_k_means, img_paysage_e2000_methode_naive, img_paysage_e2000_fourier_YCbCr, img_paysage_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 65140.37
erreur_moyenne : 8.11
pourcentage_erreur : 8.11
------ Octree ------
erreur_totale : 79675.78
erreur_moyenne : 9.92
pourcentage_erreur : 9.92
------ Kmeans ------
erreur_totale : 59421.05
erreur_moyenne : 7.4
pourcentage_erreur : 7.4
------ Naive ------
erreur_totale : 125363.96
erreur_moyenne : 15.61
pourcentage_erreur : 15.61
------ YCbCr ------
erreur_totale : 166862.36
erreur_moyenne : 20.78
pourcentage_erreur : 20.78
------ RGB ------
erreur_totale : 186913.88
erreur_moyenne : 23.28
pourcentage_erreur : 23.28

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = distance_euclid
img_repetitif = Image.open("motif_repetitif.png").convert("RGB")

img_repetitif_euclid_median_cut = recoloriage_MedianCut(img_repetitif, n, choix_distance)
img_repetitif_euclid_octree, pallette_octree = image_octree(img_repetitif, k, choix_distance)
img_repetitif_euclid_k_means = kmeans(img_repetitif, k, nb_iter, choix_distance)

img_repetitif_euclid_methode_naive, palette_naive = methode_naive(img_repetitif, choix_distance,k)
img_repetitif_euclid_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_repetitif, mode="YCbCr", k=k)
img_repetitif_euclid_fourier_RGB, palette_RGB = traitement_image_par_mode(img_repetitif, mode="RGB", k=k)

images_repetitif_euclid = [img_repetitif.convert("RGB"), img_repetitif_euclid_median_cut, img_repetitif_euclid_octree, img_repetitif_euclid_k_means,
          img_repetitif_euclid_methode_naive, img_repetitif_euclid_fourier_YCbCr, img_repetitif_euclid_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_repetitif_euclid)):
    axs[i].imshow(images_repetitif_euclid[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_repetitif_euclid_median_cut = difference(img_repetitif, img_repetitif_euclid_median_cut, choix_distance)
diff_repetitif_euclid_octree = difference(img_repetitif, img_repetitif_euclid_octree, choix_distance)
diff_repetitif_euclid_k_means = difference(img_repetitif, img_repetitif_euclid_k_means, choix_distance)

diff_repetitif_euclid_methode_naive = difference(img_repetitif, img_repetitif_euclid_methode_naive, choix_distance)
diff_repetitif_euclid_fourier_YCbCr = difference(img_repetitif, img_repetitif_euclid_fourier_YCbCr, choix_distance)
diff_repetitif_euclid_fourier_RGB = difference(img_repetitif, img_repetitif_euclid_fourier_RGB, choix_distance)

diff_repetitif_euclid = [diff_repetitif_euclid_median_cut, diff_repetitif_euclid_octree, diff_repetitif_euclid_k_means,
          diff_repetitif_euclid_methode_naive, diff_repetitif_euclid_fourier_YCbCr, diff_repetitif_euclid_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_repetitif_euclid)):
    axs[i].imshow(diff_repetitif_euclid[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_repetitif, img_repetitif_euclid_median_cut, img_repetitif_euclid_octree, img_repetitif_euclid_k_means, img_repetitif_euclid_methode_naive, img_repetitif_euclid_fourier_YCbCr, img_repetitif_euclid_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_euclid)

------ Median Cut ------
erreur_totale : 547580.26
erreur_moyenne : 27.94
pourcentage_erreur : 6.33
------ Octree ------
erreur_totale : 688811.75
erreur_moyenne : 35.14
pourcentage_erreur : 7.96
------ Kmeans ------
erreur_totale : 497992.78
erreur_moyenne : 25.41
pourcentage_erreur : 5.75
------ Naive ------
erreur_totale : 961737.03
erreur_moyenne : 49.07
pourcentage_erreur : 11.11
------ YCbCr ------
erreur_totale : 1941203.86
erreur_moyenne : 99.04
pourcentage_erreur : 22.42
------ RGB ------
erreur_totale : 1383872.2
erreur_moyenne : 70.61
pourcentage_erreur : 15.99

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = distance_lab
img_repetitif = Image.open("motif_repetitif.png").convert("RGB")

img_repetitif_e76_median_cut = recoloriage_MedianCut(img_repetitif, n, choix_distance)
img_repetitif_e76_octree, pallette_octree = image_octree(img_repetitif, k, choix_distance)
img_repetitif_e76_k_means = kmeans(img_repetitif, k, nb_iter, choix_distance)

img_repetitif_e76_methode_naive, palette_naive = methode_naive(img_repetitif, choix_distance,k)
img_repetitif_e76_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_repetitif, mode="YCbCr", k=k)
img_repetitif_e76_fourier_RGB, palette_RGB = traitement_image_par_mode(img_repetitif, mode="RGB", k=k)

images_repetitif_e76 = [img_repetitif.convert("RGB"), img_repetitif_e76_median_cut, img_repetitif_e76_octree, img_repetitif_e76_k_means,
          img_repetitif_e76_methode_naive, img_repetitif_e76_fourier_YCbCr, img_repetitif_e76_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_repetitif_e76)):
    axs[i].imshow(images_repetitif_e76[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_repetitif_e76_median_cut = difference(img_repetitif, img_repetitif_e76_median_cut, choix_distance)
diff_repetitif_e76_octree = difference(img_repetitif, img_repetitif_e76_octree, choix_distance)
diff_repetitif_e76_k_means = difference(img_repetitif, img_repetitif_e76_k_means, choix_distance)

diff_repetitif_e76_methode_naive = difference(img_repetitif, img_repetitif_e76_methode_naive, choix_distance)
diff_repetitif_e76_fourier_YCbCr = difference(img_repetitif, img_repetitif_e76_fourier_YCbCr, choix_distance)
diff_repetitif_e76_fourier_RGB = difference(img_repetitif, img_repetitif_e76_fourier_RGB, choix_distance)

diff_repetitif_e76 = [diff_repetitif_e76_median_cut, diff_repetitif_e76_octree, diff_repetitif_e76_k_means,
          diff_repetitif_e76_methode_naive, diff_repetitif_e76_fourier_YCbCr, diff_repetitif_e76_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_repetitif_e76)):
    axs[i].imshow(diff_repetitif_e76[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_repetitif, img_repetitif_e76_median_cut, img_repetitif_e76_octree, img_repetitif_e76_k_means, img_repetitif_e76_methode_naive, img_repetitif_e76_fourier_YCbCr, img_repetitif_e76_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_lab)

------ Median Cut ------
erreur_totale : 195255.44
erreur_moyenne : 9.96
pourcentage_erreur : 9.96
------ Octree ------
erreur_totale : 266578.35
erreur_moyenne : 13.6
pourcentage_erreur : 13.6
------ Kmeans ------
erreur_totale : 177785.9
erreur_moyenne : 9.07
pourcentage_erreur : 9.07
------ Naive ------
erreur_totale : 323172.2
erreur_moyenne : 16.49
pourcentage_erreur : 16.49
------ YCbCr ------
erreur_totale : 583722.52
erreur_moyenne : 29.78
pourcentage_erreur : 29.78
------ RGB ------
erreur_totale : 577031.34
erreur_moyenne : 29.44
pourcentage_erreur : 29.44

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_repetitif = Image.open("motif_repetitif.png").convert("RGB")

img_repetitif_e2000_median_cut = recoloriage_MedianCut(img_repetitif, n, choix_distance)
img_repetitif_e2000_octree, pallette_octree = image_octree(img_repetitif, k, choix_distance)
img_repetitif_e2000_k_means = kmeans(img_repetitif, k, nb_iter, choix_distance)

img_repetitif_e2000_methode_naive, palette_naive = methode_naive(img_repetitif, choix_distance,k)
img_repetitif_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_repetitif, mode="YCbCr", k=k)
img_repetitif_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_repetitif, mode="RGB", k=k)

images_repetitif_e2000 = [img_repetitif.convert("RGB"), img_repetitif_e2000_median_cut, img_repetitif_e2000_octree, img_repetitif_e2000_k_means,
          img_repetitif_e2000_methode_naive, img_repetitif_e2000_fourier_YCbCr, img_repetitif_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_repetitif_e2000)):
    axs[i].imshow(images_repetitif_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_repetitif_e2000_median_cut = difference(img_repetitif, img_repetitif_e2000_median_cut, choix_distance)
diff_repetitif_e2000_octree = difference(img_repetitif, img_repetitif_e2000_octree, choix_distance)
diff_repetitif_e2000_k_means = difference(img_repetitif, img_repetitif_e2000_k_means, choix_distance)

diff_repetitif_e2000_methode_naive = difference(img_repetitif, img_repetitif_e2000_methode_naive, choix_distance)
diff_repetitif_e2000_fourier_YCbCr = difference(img_repetitif, img_repetitif_e2000_fourier_YCbCr, choix_distance)
diff_repetitif_e2000_fourier_RGB = difference(img_repetitif, img_repetitif_e2000_fourier_RGB, choix_distance)

diff_repetitif_e2000 = [diff_repetitif_e2000_median_cut, diff_repetitif_e2000_octree, diff_repetitif_e2000_k_means,
          diff_repetitif_e2000_methode_naive, diff_repetitif_e2000_fourier_YCbCr, diff_repetitif_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_repetitif_e2000)):
    axs[i].imshow(diff_repetitif_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_repetitif, img_repetitif_e2000_median_cut, img_repetitif_e2000_octree, img_repetitif_e2000_k_means, img_repetitif_e2000_methode_naive, img_repetitif_e2000_fourier_YCbCr, img_repetitif_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 102759.24
erreur_moyenne : 5.24
pourcentage_erreur : 5.24
------ Octree ------
erreur_totale : 144696.77
erreur_moyenne : 7.38
pourcentage_erreur : 7.38
------ Kmeans ------
erreur_totale : 90956.13
erreur_moyenne : 4.64
pourcentage_erreur : 4.64
------ Naive ------
erreur_totale : 158807.26
erreur_moyenne : 8.1
pourcentage_erreur : 8.1
------ YCbCr ------
erreur_totale : 307231.04
erreur_moyenne : 15.68
pourcentage_erreur : 15.68
------ RGB ------
erreur_totale : 371003.41
erreur_moyenne : 18.93
pourcentage_erreur : 18.93

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_festival = Image.open("festival.png").convert("RGB")

img_festival_e2000_median_cut = recoloriage_MedianCut(img_festival, n, choix_distance)
img_festival_e2000_octree, pallette_octree = image_octree(img_festival, k, choix_distance)
img_festival_e2000_k_means = kmeans(img_festival, k, nb_iter, choix_distance)

img_festival_e2000_methode_naive, palette_naive = methode_naive(img_festival, choix_distance,k)
img_festival_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_festival, mode="YCbCr", k=k)
img_festival_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_festival, mode="RGB", k=k)

images_festival_e2000 = [img_festival.convert("RGB"), img_festival_e2000_median_cut, img_festival_e2000_octree, img_festival_e2000_k_means,
          img_festival_e2000_methode_naive, img_festival_e2000_fourier_YCbCr, img_festival_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_festival_e2000)):
    axs[i].imshow(images_festival_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_festival_e2000_median_cut = difference(img_repetitif, img_festival_e2000_median_cut, choix_distance)
diff_festival_e2000_octree = difference(img_repetitif, img_festival_e2000_octree, choix_distance)
diff_festival_e2000_k_means = difference(img_repetitif, img_festival_e2000_k_means, choix_distance)

diff_festival_e2000_methode_naive = difference(img_repetitif, img_festival_e2000_methode_naive, choix_distance)
diff_festival_e2000_fourier_YCbCr = difference(img_repetitif, img_festival_e2000_fourier_YCbCr, choix_distance)
diff_festival_e2000_fourier_RGB = difference(img_repetitif, img_festival_e2000_fourier_RGB, choix_distance)

diff_festival_e2000 = [diff_festival_e2000_median_cut, diff_festival_e2000_octree, diff_festival_e2000_k_means,
          diff_festival_e2000_methode_naive, diff_festival_e2000_fourier_YCbCr, diff_festival_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]

fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_festival_e2000)):
    axs[i].imshow(diff_festival_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_festival, img_festival_e2000_median_cut, img_festival_e2000_octree, img_festival_e2000_k_means, img_festival_e2000_methode_naive, img_festival_e2000_fourier_YCbCr, img_festival_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], distance_euclid)

------ Median Cut ------
erreur_totale : 3500644.54
erreur_moyenne : 43.8
pourcentage_erreur : 9.92
------ Octree ------
erreur_totale : 3928679.26
erreur_moyenne : 49.15
pourcentage_erreur : 11.13
------ Kmeans ------
erreur_totale : 3242244.05
erreur_moyenne : 40.57
pourcentage_erreur : 9.18
------ Naive ------
erreur_totale : 8702496.16
erreur_moyenne : 108.88
pourcentage_erreur : 24.65
------ YCbCr ------
erreur_totale : 9890472.5
erreur_moyenne : 123.75
pourcentage_erreur : 28.02
------ RGB ------
erreur_totale : 7065169.59
erreur_moyenne : 88.4
pourcentage_erreur : 20.01

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_flowers = Image.open("Flowers.png").convert("RGB")

img_flowers_e2000_median_cut = recoloriage_MedianCut(img_flowers, n, choix_distance)
img_flowers_e2000_octree, pallette_octree = image_octree(img_flowers, k, choix_distance)
img_flowers_e2000_k_means = kmeans(img_flowers, k, nb_iter, choix_distance)

img_flowers_e2000_methode_naive, palette_naive = methode_naive(img_flowers, choix_distance,k)
img_flowers_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_flowers, mode="YCbCr", k=k)
img_flowers_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_flowers, mode="RGB", k=k)

images_flowers_e2000 = [img_flowers.convert("RGB"), img_flowers_e2000_median_cut, img_flowers_e2000_octree, img_flowers_e2000_k_means,
          img_flowers_e2000_methode_naive, img_flowers_e2000_fourier_YCbCr, img_flowers_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_flowers_e2000)):
    axs[i].imshow(images_flowers_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_flowers_e2000_median_cut = difference(img_flowers, img_flowers_e2000_median_cut, choix_distance)
diff_flowers_e2000_octree = difference(img_flowers, img_flowers_e2000_octree, choix_distance)
diff_flowers_e2000_k_means = difference(img_flowers, img_flowers_e2000_k_means, choix_distance)

diff_flowers_e2000_methode_naive = difference(img_flowers, img_flowers_e2000_methode_naive, choix_distance)
diff_flowers_e2000_fourier_YCbCr = difference(img_flowers, img_flowers_e2000_fourier_YCbCr, choix_distance)
diff_flowers_e2000_fourier_RGB = difference(img_flowers, img_flowers_e2000_fourier_RGB, choix_distance)

diff_flowers_e2000 = [diff_flowers_e2000_median_cut, diff_flowers_e2000_octree, diff_flowers_e2000_k_means,
          diff_flowers_e2000_methode_naive, diff_flowers_e2000_fourier_YCbCr, diff_flowers_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_flowers_e2000)):
    axs[i].imshow(diff_flowers_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_flowers, img_flowers_e2000_median_cut, img_flowers_e2000_octree, img_flowers_e2000_k_means, img_flowers_e2000_methode_naive, img_flowers_e2000_fourier_YCbCr, img_flowers_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 3592395.95
erreur_moyenne : 2.72
pourcentage_erreur : 2.72
------ Octree ------
erreur_totale : 5127391.99
erreur_moyenne : 3.88
pourcentage_erreur : 3.88
------ Kmeans ------
erreur_totale : 2249500.89
erreur_moyenne : 1.7
pourcentage_erreur : 1.7
------ Naive ------
erreur_totale : 2596610.87
erreur_moyenne : 1.96
pourcentage_erreur : 1.96
------ YCbCr ------
erreur_totale : 17730987.63
erreur_moyenne : 13.4
pourcentage_erreur : 13.4
------ RGB ------
erreur_totale : 21935133.03
erreur_moyenne : 16.58
pourcentage_erreur : 16.58

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_robots = Image.open("robot.jpg").convert("RGB")

img_robots_e2000_median_cut = recoloriage_MedianCut(img_robots, n, choix_distance)
img_robots_e2000_octree, pallette_octree = image_octree(img_robots, k, choix_distance)
img_robots_e2000_k_means = kmeans(img_robots, k, nb_iter, choix_distance)

img_robots_e2000_methode_naive, palette_naive = methode_naive(img_robots, choix_distance,k)
img_robots_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_robots, mode="YCbCr", k=k)
img_robots_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_robots, mode="RGB", k=k)

images_robots_e2000 = [img_robots.convert("RGB"), img_robots_e2000_median_cut, img_robots_e2000_octree, img_robots_e2000_k_means,
          img_robots_e2000_methode_naive, img_robots_e2000_fourier_YCbCr, img_robots_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_robots_e2000)):
    axs[i].imshow(images_robots_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_robots_e2000_median_cut = difference(img_robots, img_robots_e2000_median_cut, choix_distance)
diff_robots_e2000_octree = difference(img_robots, img_robots_e2000_octree, choix_distance)
diff_robots_e2000_k_means = difference(img_robots, img_robots_e2000_k_means, choix_distance)

diff_robots_e2000_methode_naive = difference(img_robots, img_robots_e2000_methode_naive, choix_distance)
diff_robots_e2000_fourier_YCbCr = difference(img_robots, img_robots_e2000_fourier_YCbCr, choix_distance)
diff_robots_e2000_fourier_RGB = difference(img_robots, img_robots_e2000_fourier_RGB, choix_distance)

diff_robots_e2000 = [diff_robots_e2000_median_cut, diff_robots_e2000_octree, diff_robots_e2000_k_means,
          diff_robots_e2000_methode_naive, diff_robots_e2000_fourier_YCbCr, diff_robots_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_robots_e2000)):
    axs[i].imshow(diff_robots_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_robots, img_robots_e2000_median_cut, img_robots_e2000_octree, img_robots_e2000_k_means, img_robots_e2000_methode_naive, img_robots_e2000_fourier_YCbCr, img_robots_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 1791745.99
erreur_moyenne : 4.27
pourcentage_erreur : 4.27
------ Octree ------
erreur_totale : 2827239.42
erreur_moyenne : 6.73
pourcentage_erreur : 6.73
------ Kmeans ------
erreur_totale : 1770123.29
erreur_moyenne : 4.21
pourcentage_erreur : 4.21
------ Naive ------
erreur_totale : 4587743.04
erreur_moyenne : 10.92
pourcentage_erreur : 10.92
------ YCbCr ------
erreur_totale : 7968298.33
erreur_moyenne : 18.97
pourcentage_erreur : 18.97
------ RGB ------
erreur_totale : 7558520.16
erreur_moyenne : 18.0
pourcentage_erreur : 18.0

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_texture_fine = Image.open("texture_fine.png").convert("RGB")

img_texture_fine_e2000_median_cut = recoloriage_MedianCut(img_texture_fine, n, choix_distance)
img_texture_fine_e2000_octree, pallette_octree = image_octree(img_texture_fine, k, choix_distance)
img_texture_fine_e2000_k_means = kmeans(img_texture_fine, k, nb_iter, choix_distance)

img_texture_fine_e2000_methode_naive, palette_naive = methode_naive(img_texture_fine, choix_distance,k)
img_texture_fine_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_texture_fine, mode="YCbCr", k=k)
img_texture_fine_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_texture_fine, mode="RGB", k=k)

images_texture_fine_e2000 = [img_texture_fine.convert("RGB"), img_texture_fine_e2000_median_cut, img_texture_fine_e2000_octree, img_texture_fine_e2000_k_means,
          img_texture_fine_e2000_methode_naive, img_texture_fine_e2000_fourier_YCbCr, img_texture_fine_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_texture_fine_e2000)):
    axs[i].imshow(images_texture_fine_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_img_texture_fine_e2000_median_cut = difference(img_texture_fine, img_texture_fine_e2000_median_cut, choix_distance)
diff_img_texture_fine_e2000_octree = difference(img_texture_fine, img_texture_fine_e2000_octree, choix_distance)
diff_img_texture_fine_e2000_k_means = difference(img_texture_fine, img_texture_fine_e2000_k_means, choix_distance)

diff_img_texture_fine_e2000_methode_naive = difference(img_texture_fine, img_texture_fine_e2000_methode_naive, choix_distance)
diff_img_texture_fine_e2000_fourier_YCbCr = difference(img_texture_fine, img_texture_fine_e2000_fourier_YCbCr, choix_distance)
diff_img_texture_fine_e2000_fourier_RGB = difference(img_texture_fine, img_texture_fine_e2000_fourier_RGB, choix_distance)

diff_img_texture_fine_e2000 = [diff_img_texture_fine_e2000_median_cut, diff_img_texture_fine_e2000_octree, diff_img_texture_fine_e2000_k_means,
          diff_img_texture_fine_e2000_methode_naive, diff_img_texture_fine_e2000_fourier_YCbCr, diff_img_texture_fine_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_img_texture_fine_e2000)):
    axs[i].imshow(diff_img_texture_fine_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_texture_fine, img_texture_fine_e2000_median_cut, img_texture_fine_e2000_octree, img_texture_fine_e2000_k_means, img_texture_fine_e2000_methode_naive, img_texture_fine_e2000_fourier_YCbCr, img_texture_fine_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 220772.97
erreur_moyenne : 0.84
pourcentage_erreur : 0.84
------ Octree ------
erreur_totale : 248558.19
erreur_moyenne : 0.95
pourcentage_erreur : 0.95
------ Kmeans ------
erreur_totale : 216047.1
erreur_moyenne : 0.83
pourcentage_erreur : 0.83
------ Naive ------
erreur_totale : 504794.12
erreur_moyenne : 1.93
pourcentage_erreur : 1.93
------ YCbCr ------
erreur_totale : 1743295.86
erreur_moyenne : 6.66
pourcentage_erreur : 6.66
------ RGB ------
erreur_totale : 656391.36
erreur_moyenne : 2.51
pourcentage_erreur : 2.51

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_architecture = Image.open("architecture.png").convert("RGB")

img_architecture_e2000_median_cut = recoloriage_MedianCut(img_architecture, n, choix_distance)
img_architecture_e2000_octree, pallette_octree = image_octree(img_architecture, k, choix_distance)
img_architecture_e2000_k_means = kmeans(img_architecture, k, nb_iter, choix_distance)

img_architecture_e2000_methode_naive, palette_naive = methode_naive(img_architecture, choix_distance,k)
img_architecture_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_architecture, mode="YCbCr", k=k)
img_architecture_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_architecture, mode="RGB", k=k)

images_architecture_e2000 = [img_architecture.convert("RGB"), img_architecture_e2000_median_cut, img_architecture_e2000_octree, img_architecture_e2000_k_means,
          img_architecture_e2000_methode_naive, img_architecture_e2000_fourier_YCbCr, img_architecture_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_architecture_e2000)):
    axs[i].imshow(images_architecture_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_architecture_e2000_median_cut = difference(img_architecture, img_architecture_e2000_median_cut, choix_distance)
diff_architecture_e2000_octree = difference(img_architecture, img_architecture_e2000_octree, choix_distance)
diff_architecture_e2000_k_means = difference(img_architecture, img_architecture_e2000_k_means, choix_distance)

diff_architecture_e2000_methode_naive = difference(img_architecture, img_architecture_e2000_methode_naive, choix_distance)
diff_architecture_e2000_fourier_YCbCr = difference(img_architecture, img_architecture_e2000_fourier_YCbCr, choix_distance)
diff_architecture_e2000_fourier_RGB = difference(img_architecture, img_architecture_e2000_fourier_RGB, choix_distance)

diff_img_architecture_e2000 = [diff_architecture_e2000_median_cut, diff_architecture_e2000_octree, diff_architecture_e2000_k_means,
          diff_architecture_e2000_methode_naive, diff_architecture_e2000_fourier_YCbCr, diff_architecture_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_img_architecture_e2000)):
    axs[i].imshow(diff_img_architecture_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_architecture, img_architecture_e2000_median_cut, img_architecture_e2000_octree, img_architecture_e2000_k_means, img_architecture_e2000_methode_naive, img_architecture_e2000_fourier_YCbCr, img_architecture_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 1178251.25
erreur_moyenne : 4.51
pourcentage_erreur : 4.51
------ Octree ------
erreur_totale : 1866531.3
erreur_moyenne : 7.15
pourcentage_erreur : 7.15
------ Kmeans ------
erreur_totale : 1442262.08
erreur_moyenne : 5.53
pourcentage_erreur : 5.53
------ Naive ------
erreur_totale : 5517185.2
erreur_moyenne : 21.14
pourcentage_erreur : 21.14
------ YCbCr ------
erreur_totale : 5042189.18
erreur_moyenne : 19.32
pourcentage_erreur : 19.32
------ RGB ------
erreur_totale : 4685642.32
erreur_moyenne : 17.95
pourcentage_erreur : 17.95

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000
img_homme = Image.open("homme.jpg").convert("RGB")

img_homme_e2000_median_cut = recoloriage_MedianCut(img_homme, n, choix_distance)
img_homme_e2000_octree, pallette_octree = image_octree(img_homme, k, choix_distance)
img_homme_e2000_k_means = kmeans(img_homme, k, nb_iter, choix_distance)

img_homme_e2000_methode_naive, palette_naive = methode_naive(img_homme, choix_distance,k)
img_homme_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(img_homme, mode="YCbCr", k=k)
img_homme_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(img_homme, mode="RGB", k=k)

images_homme_e2000 = [img_homme.convert("RGB"), img_homme_e2000_median_cut, img_homme_e2000_octree, img_homme_e2000_k_means,
          img_homme_e2000_methode_naive, img_homme_e2000_fourier_YCbCr, img_homme_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_homme_e2000)):
    axs[i].imshow(images_homme_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_homme_e2000_median_cut = difference(img_homme, img_homme_e2000_median_cut, choix_distance)
diff_homme_e2000_octree = difference(img_homme, img_homme_e2000_octree, choix_distance)
diff_homme_e2000_k_means = difference(img_homme, img_homme_e2000_k_means, choix_distance)

diff_homme_e2000_methode_naive = difference(img_homme, img_homme_e2000_methode_naive, choix_distance)
diff_homme_e2000_fourier_YCbCr = difference(img_homme, img_homme_e2000_fourier_YCbCr, choix_distance)
diff_homme_e2000_fourier_RGB = difference(img_homme, img_homme_e2000_fourier_RGB, choix_distance)

diff_img_homme_e2000 = [diff_homme_e2000_median_cut, diff_homme_e2000_octree, diff_homme_e2000_k_means,
          diff_homme_e2000_methode_naive, diff_homme_e2000_fourier_YCbCr, diff_homme_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_img_homme_e2000)):
    axs[i].imshow(diff_img_homme_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(img_homme, img_homme_e2000_median_cut, img_homme_e2000_octree, img_homme_e2000_k_means, img_homme_e2000_methode_naive, img_homme_e2000_fourier_YCbCr, img_homme_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 9820182.63
erreur_moyenne : 5.76
pourcentage_erreur : 5.76
------ Octree ------
erreur_totale : 11654630.49
erreur_moyenne : 6.83
pourcentage_erreur : 6.83
------ Kmeans ------
erreur_totale : 9041595.39
erreur_moyenne : 5.3
pourcentage_erreur : 5.3
------ Naive ------
erreur_totale : 22086127.09
erreur_moyenne : 12.95
pourcentage_erreur : 12.95
------ YCbCr ------
erreur_totale : 35002663.13
erreur_moyenne : 20.52
pourcentage_erreur : 20.52
------ RGB ------
erreur_totale : 35845507.38
erreur_moyenne : 21.02
pourcentage_erreur : 21.02

# On ouvre l'image de test
image_homme = Image.open("homme.jpg").convert("RGB")
# On applique le flou gaussien
image_homme_flou_gaussien = convolution(image_homme, gauss3)
image_homme_flou_gaussien_2 = convolution(image_homme, gauss7)

# Affichage
fig, axs = plt.subplots(1, 3, figsize=(15, 5))
axs[0].imshow(image_homme)
axs[0].set_title("Image originale")
axs[0].axis('off')

axs[1].imshow(image_homme_flou_gaussien)
axs[1].set_title("Image avec flou gaussien : noyau 3x3")
axs[1].axis('off')

axs[2].imshow(image_homme_flou_gaussien_2)
axs[2].set_title("Image avec flou gaussien : noyau 7x7")
axs[2].axis('off')

plt.tight_layout()
plt.show()

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000

image_homme_flou_gaussien_e2000_median_cut = recoloriage_MedianCut(image_homme_flou_gaussien, n, choix_distance)
image_homme_flou_gaussien_e2000_octree, pallette_octree = image_octree(image_homme_flou_gaussien, k, choix_distance)
image_homme_flou_gaussien_e2000_k_means = kmeans(image_homme_flou_gaussien, k, nb_iter, choix_distance)

image_homme_flou_gaussien_e2000_methode_naive, palette_naive = methode_naive(image_homme_flou_gaussien, choix_distance,k)
image_homme_flou_gaussien_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(image_homme_flou_gaussien, mode="YCbCr", k=k)
image_homme_flou_gaussien_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(image_homme_flou_gaussien, mode="RGB", k=k)

images_homme_flou_gaussien_e2000 = [image_homme_flou_gaussien.convert("RGB"), image_homme_flou_gaussien_e2000_median_cut, image_homme_flou_gaussien_e2000_octree, image_homme_flou_gaussien_e2000_k_means,
          image_homme_flou_gaussien_e2000_methode_naive, image_homme_flou_gaussien_e2000_fourier_YCbCr, image_homme_flou_gaussien_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_homme_flou_gaussien_e2000)):
    axs[i].imshow(images_homme_flou_gaussien_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_homme_flou_gaussien_e2000_median_cut = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_e2000_median_cut, choix_distance)
diff_homme_flou_gaussien_e2000_octree = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_e2000_octree, choix_distance)
diff_homme_flou_gaussien_e2000_k_means = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_e2000_k_means, choix_distance)

diff_homme_flou_gaussien_e2000_methode_naive = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_e2000_methode_naive, choix_distance)
diff_homme_flou_gaussien_e2000_fourier_YCbCr = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_e2000_fourier_YCbCr, choix_distance)
diff_homme_flou_gaussien_e2000_fourier_RGB = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_e2000_fourier_RGB, choix_distance)

diff_img_homme_flou_gaussien_e2000 = [diff_homme_flou_gaussien_e2000_median_cut, diff_homme_flou_gaussien_e2000_octree, diff_homme_flou_gaussien_e2000_k_means,
          diff_homme_flou_gaussien_e2000_methode_naive, diff_homme_flou_gaussien_e2000_fourier_YCbCr, diff_homme_flou_gaussien_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_img_homme_flou_gaussien_e2000)):
    axs[i].imshow(diff_img_homme_flou_gaussien_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(image_homme, image_homme_flou_gaussien_e2000_median_cut, image_homme_flou_gaussien_e2000_octree, image_homme_flou_gaussien_e2000_k_means, image_homme_flou_gaussien_e2000_methode_naive, image_homme_flou_gaussien_e2000_fourier_YCbCr, image_homme_flou_gaussien_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 9282781.73
erreur_moyenne : 5.44
pourcentage_erreur : 5.44
------ Octree ------
erreur_totale : 11636250.26
erreur_moyenne : 6.82
pourcentage_erreur : 6.82
------ Kmeans ------
erreur_totale : 9059031.14
erreur_moyenne : 5.31
pourcentage_erreur : 5.31
------ Naive ------
erreur_totale : 22413550.8
erreur_moyenne : 13.14
pourcentage_erreur : 13.14
------ YCbCr ------
erreur_totale : 35043002.94
erreur_moyenne : 20.55
pourcentage_erreur : 20.55
------ RGB ------
erreur_totale : 35718132.86
erreur_moyenne : 20.94
pourcentage_erreur : 20.94

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000

image_homme_flou_gaussien_2_e2000_median_cut = recoloriage_MedianCut(image_homme_flou_gaussien_2, n, choix_distance)
image_homme_flou_gaussien_2_e2000_octree, pallette_octree = image_octree(image_homme_flou_gaussien_2, k, choix_distance)
image_homme_flou_gaussien_2_e2000_k_means = kmeans(image_homme_flou_gaussien_2, k, nb_iter, choix_distance)

image_homme_flou_gaussien_2_e2000_methode_naive, palette_naive = methode_naive(image_homme_flou_gaussien_2, choix_distance,k)
image_homme_flou_gaussien_2_e2000_fourier_YCbCr, palette_YCbCr = traitement_image_par_mode(image_homme_flou_gaussien_2, mode="YCbCr", k=k)
image_homme_flou_gaussien_2_e2000_fourier_RGB, palette_RGB = traitement_image_par_mode(image_homme_flou_gaussien_2, mode="RGB", k=k)

images_homme_flou_gaussien_2_e2000 = [image_homme_flou_gaussien_2.convert("RGB"), image_homme_flou_gaussien_2_e2000_median_cut, image_homme_flou_gaussien_2_e2000_octree, image_homme_flou_gaussien_e2000_k_means,
          image_homme_flou_gaussien_2_e2000_methode_naive, image_homme_flou_gaussien_2_e2000_fourier_YCbCr, image_homme_flou_gaussien_2_e2000_fourier_RGB]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_homme_flou_gaussien_2_e2000)):
    axs[i].imshow(images_homme_flou_gaussien_2_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_homme_flou_gaussien_2_e2000_median_cut = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_2_e2000_median_cut, choix_distance)
diff_homme_flou_gaussien_2_e2000_octree = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_2_e2000_octree, choix_distance)
diff_homme_flou_gaussien_2_e2000_k_means = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_2_e2000_k_means, choix_distance)

diff_homme_flou_gaussien_2_e2000_methode_naive = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_2_e2000_methode_naive, choix_distance)
diff_homme_flou_gaussien_2_e2000_fourier_YCbCr = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_2_e2000_fourier_YCbCr, choix_distance)
diff_homme_flou_gaussien_2_e2000_fourier_RGB = difference(image_homme_flou_gaussien, image_homme_flou_gaussien_2_e2000_fourier_RGB, choix_distance)

diff_img_homme_flou_gaussien_2_e2000 = [diff_homme_flou_gaussien_2_e2000_median_cut, diff_homme_flou_gaussien_2_e2000_octree, diff_homme_flou_gaussien_2_e2000_k_means,
          diff_homme_flou_gaussien_2_e2000_methode_naive, diff_homme_flou_gaussien_2_e2000_fourier_YCbCr, diff_homme_flou_gaussien_2_e2000_fourier_RGB]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier RGB"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_img_homme_flou_gaussien_2_e2000)):
    axs[i].imshow(diff_img_homme_flou_gaussien_2_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(image_homme, image_homme_flou_gaussien_2_e2000_median_cut, image_homme_flou_gaussien_2_e2000_octree, image_homme_flou_gaussien_2_e2000_k_means, image_homme_flou_gaussien_2_e2000_methode_naive, image_homme_flou_gaussien_2_e2000_fourier_YCbCr, image_homme_flou_gaussien_2_e2000_fourier_RGB, ["Median Cut", "Octree", "Kmeans", "Naive", "YCbCr", "RGB"], delta_e_2000)

------ Median Cut ------
erreur_totale : 9906948.99
erreur_moyenne : 5.81
pourcentage_erreur : 5.81
------ Octree ------
erreur_totale : 11712885.8
erreur_moyenne : 6.87
pourcentage_erreur : 6.87
------ Kmeans ------
erreur_totale : 9057647.48
erreur_moyenne : 5.31
pourcentage_erreur : 5.31
------ Naive ------
erreur_totale : 22451962.69
erreur_moyenne : 13.16
pourcentage_erreur : 13.16
------ YCbCr ------
erreur_totale : 36051489.55
erreur_moyenne : 21.14
pourcentage_erreur : 21.14
------ RGB ------
erreur_totale : 35718034.81
erreur_moyenne : 20.94
pourcentage_erreur : 20.94

img_sobel_architecture = Image.open("architecture.png")
gx_sobel_architecture = convolution_sobel(img_sobel_architecture, sobelx3)
gy_sobel_architecture = convolution_sobel(img_sobel_architecture, sobely3)
mag_sobel_architecture = magnitude_gradient(gx_sobel_architecture, gy_sobel_architecture)
mag_sobel_architecture_thresh = seuillage(mag_sobel_architecture, seuil=142) # Attention à ne pas choisir un seuil trop élevé ni trop faible


fig, axs = plt.subplots(1, 3, figsize=(20, 5))

images_sobel_architecture = [img_sobel_architecture.convert("L"), mag_sobel_architecture, mag_sobel_architecture_thresh]
titles_sobel_architecture = ["Image originale (niveaux de gris)", "Magnitude", "Contours (avec seuil)"]

for ax, im, title in zip(axs, images_sobel_architecture, titles_sobel_architecture):
    ax.imshow(im, cmap='gray')
    ax.set_title(title)
    ax.axis("off")

plt.tight_layout()
plt.show()

k=8
nb_iter=10
n=math.floor(math.log(k)/math.log(2))
choix_distance = delta_e_2000

img_architecture_sobel_e2000_median_cut = recoloriage_MedianCut(mag_sobel_architecture_thresh.convert("RGB"), n, choix_distance)
img_architecture_sobel_e2000_octree, pallette_octree = image_octree(mag_sobel_architecture_thresh.convert("RGB"), k, choix_distance)
img_architecture_sobel_e2000_k_means = kmeans(mag_sobel_architecture_thresh.convert("RGB"), k, nb_iter, choix_distance)

img_architecture_sobel_e2000_methode_naive, palette_naive = methode_naive(mag_sobel_architecture_thresh.convert("RGB"), choix_distance,k)
img_architecture_sobel_e2000_fourier_grayscale, palette_YCbCr = traitement_image_par_mode(mag_sobel_architecture_thresh, mode="grayscale", k=k)
img_architecture_sobel_e2000_fourier_YCbCr, palette_RGB = traitement_image_par_mode(mag_sobel_architecture_thresh.convert("RGB"), mode="YCbCr", k=k)

images_architecture_sobel_e2000 = [mag_sobel_architecture_thresh, img_architecture_sobel_e2000_median_cut, img_architecture_sobel_e2000_octree, img_architecture_sobel_e2000_k_means,
          img_architecture_sobel_e2000_methode_naive, img_architecture_sobel_e2000_fourier_grayscale, img_architecture_sobel_e2000_fourier_YCbCr]

titles = ["Image originale", "Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier Grayscale", "Fourier YCbCr"]


fig, axs = plt.subplots(2, 4, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(images_architecture_sobel_e2000)):
    axs[i].imshow(images_architecture_sobel_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

diff_architecture_sobel_e2000_median_cut = difference(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_median_cut, choix_distance)
diff_architecture_sobel_e2000_octree = difference(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_octree, choix_distance)
diff_architecture_sobel_e2000_k_means = difference(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_k_means, choix_distance)

diff_architecture_sobel_e2000_methode_naive = difference(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_methode_naive, choix_distance)
diff_architecture_sobel_e2000_fourier_YCbCr = difference(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_fourier_YCbCr, choix_distance)
diff_architecture_sobel_e2000_fourier_grayscale = difference(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_fourier_grayscale.convert("RGB"), choix_distance)

diff_architecture_sobel_e2000 = [diff_architecture_sobel_e2000_median_cut, diff_architecture_sobel_e2000_octree, diff_architecture_sobel_e2000_k_means,
          diff_architecture_sobel_e2000_methode_naive, diff_architecture_sobel_e2000_fourier_YCbCr, diff_architecture_sobel_e2000_fourier_grayscale]

titles = ["Median Cut", "Octree", "K-Means",
          "Méthode naïve", "Fourier YCbCr", "Fourier Grayscale"]


fig, axs = plt.subplots(2, 3, figsize=(20, 10))


axs = axs.flatten()


for i in range(len(diff_architecture_sobel_e2000)):
    axs[i].imshow(diff_architecture_sobel_e2000[i], cmap='gray')
    axs[i].set_title(titles[i])
    axs[i].axis('off')

axs[-1].axis('off')

plt.tight_layout()
plt.show()

score_synthese(mag_sobel_architecture_thresh.convert("RGB"), img_architecture_sobel_e2000_median_cut.convert("RGB"), img_architecture_sobel_e2000_octree.convert("RGB"), img_architecture_sobel_e2000_k_means.convert("RGB"), img_architecture_sobel_e2000_methode_naive.convert("RGB"), img_architecture_sobel_e2000_fourier_grayscale.convert("RGB"), img_architecture_sobel_e2000_fourier_YCbCr.convert("RGB"), ["Median Cut", "Octree", "Kmeans", "Naive", "Fourier Grayscale", "YCbCr"], delta_e_2000)

------ Median Cut ------
erreur_totale : 643449.25
erreur_moyenne : 2.46
pourcentage_erreur : 2.46
------ Octree ------
erreur_totale : 0.0
erreur_moyenne : 0.0
pourcentage_erreur : 0.0
------ Kmeans ------
erreur_totale : 0.0
erreur_moyenne : 0.0
pourcentage_erreur : 0.0
------ Naive ------
erreur_totale : 0.0
erreur_moyenne : 0.0
pourcentage_erreur : 0.0
------ Fourier Grayscale ------
erreur_totale : 1322827.04
erreur_moyenne : 5.07
pourcentage_erreur : 5.07
------ YCbCr ------
erreur_totale : 2624496.34
erreur_moyenne : 10.05
pourcentage_erreur : 10.05

import pandas as pd
from IPython.display import display

# Liste mise à jour des images
images = [
    "Portrait",
    "Nature/paysage",
    "Palette restreinte (motif répétitif, dessin simplifié)",
    "Couleurs Vives",
    "Couleurs ternes",
    "Texture fine",
    "Architecture",
    "Architecture avec Filtre Sobel + contours",
    "Homme",
    "Homme avec Flou gaussien"
]

# Colonnes des méthodes
columns = ["K-Means", "Median Cut", "Octree", "Méthode Naive", "Fourier YCbCr", "Fourier RGB", "Fourier Grayscale"]

# Création du MultiIndex
index_tuples = []
for img in images:
    index_tuples.append((img, "Description"))
    index_tuples.append((img, "Erreur moyenne par pixel"))

index = pd.MultiIndex.from_tuples(index_tuples, names=["Image", "Critère"])

# Génération de données factices réalistes
data = {
    "K-Means": [
        "Ombres et couleurs respectées", "4.6",
        "Bon compromis entre respect des couleurs et des formes", "7.23",
        "Respect des différentes tonalités de couleurs et des formes", "4.92 ; 1.73",
        "Fidèle et légère perte de contraste", "38.52",
        "Très fidèle à l'image originale", "4.35",
        "Fidèle", "0.81",
        "Très fidèle", "4.36",
        "Très fidèle", "0.0",
        "Très fidèle", "5.26",
        "Fidèle avec quelques défauts", "5.14"
    ],
    "Median Cut": [
        "Ombres et couleurs respectées", "5.07",
        "Bon compromis entre respect des couleurs et des formes", "8.11",
        "Respect des différentes tonalités de couleurs et des formes", "5.24 ; 2.72",
        "Fidèle et légère perte de contraste", "43.8",
        "Très fidèle", "4.27",
        "Fidèle", "0.84",
        "Très fidèle, bonne nuance de couleurs", "4.51",
        "Fidèle mais moins de contraste", "2.46",
        "Fidèle avec plusieurs défauts", "5.76",
        "Fidèle avec de nombreux défauts", "5.44"
    ],
    "Octree": [
        "Manque de détails", "6.5",
        "Dégradés de couleurs respectés au détriment des formes, ", "9.92",
        "Uniformisation des couleurs de l'arrière-plan", "7.38 ; 3.88",
        "Très fidèle avec quelques déauts", "49.15",
        "Fidèle mais moins de détails en arrière-plan", "6.76",
        "Précision dans les détails extraordinaire", "0.95",
        "Palette terne mais image fidèle", "7.15",
        "Très fidèle", "0.0",
        "Trsè fidèle mais forme floue", "6.83",
        "Fidèle mais forme lisse", "6.82"
    ],
    "Méthode Naive": [
        "Couleurs non fidèles", "26.69",
        "Image non fidèle", "15.61",
        "Compromis formes/couleurs", "8.1 ; 1.96",
        "Peu fidèle, palette terne", "108.88",
        "Image de type argentique", "10.92",
        "Uniformise l'image", "1.93",
        "Non fidèle, non respect de la forme générale", "21.14",
        "Très fidèle", "0.0",
        "Style différent mais fidèle", "12.95",
        "Style différent mais fidèle", "13.14"
    ],
    "Fourier YCbCr": [
        "Couleurs non fidèles", "29.19",
        "Très bonne restitution des formes générales mais ajout de nouvelles couleurs", "20.78",
        "Image de couleur quasi-uniforme / mauvaise définition des contours", "15.68 ; 13.4",
        "Image floue, non fidèle", "123.75",
        "Couleurs non fidèles", "18.97",
        "Uniformise l'image", "6.66",
        "Forme restituée mais palette terne", "19.32",
        "Image terne", "10.05",
        "Image floue, non fidèle", "20.52",
        "Flou, non fidèle", "20.55"
    ],
    "Fourier RGB": [
        "Couleurs non fidèles", "28.64",
        "Forme générale respectée mais couleurs ternes", "23.28",
        "Image de couleur quasi-uniforme / mauvaise définition des contours", "18.93 ; 16.58",
        "Img fidèle mais plus fade", "88.4",
        "Couleurs non fidèles", "18.0",
        "Uniformise l'image", "2.51",
        "Forme restituée mais palette terne", "17.95",
        "", "",
        "Image très floue, non fidèle", "21.02",
        "Très flou, non fidèle", "20.94"
    ],
    "Fourier Grayscale": [
        "", "",
        "", "",
        "", "",
        "", "",
        "", "",
        "", "",
        "", "",
        "Très fidèle", "5.07",
        "", "",
        "", ""
    ]
}

df = pd.DataFrame(data, index=index)

# Indices des lignes à séparer
separator_rows = list(range(0, len(df), 2))

# Style avec trait horizontal visible sur toute la ligne
def style_full_separators(styler):
    styles = [
        {
            "selector": f"tr:nth-child({i + 1})",  # +2 pour ignorer l'en-tête
            "props": [("border-top", "2px solid black")]
        }
        for i in separator_rows
    ]
    return styler.set_table_styles(styles)

def highlight_custom(x):
    styles = pd.DataFrame('', index=x.index, columns=x.columns)
    # Exemple de surlignage :
    styles.loc[("Portrait", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Portrait", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Portrait", "Description"), "Median Cut"] = 'background-color: lime'
    styles.loc[("Portrait", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Portrait", "Erreur moyenne par pixel"), "Fourier RGB"] = 'background-color: lightcoral'
    styles.loc[("Portrait", "Erreur moyenne par pixel"), "Méthode Naive"] = 'background-color: lightcoral'

    styles.loc[("Nature/paysage", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Nature/paysage", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Nature/paysage", "Erreur moyenne par pixel"), "Fourier RGB"] = 'background-color: lightcoral'
    styles.loc[("Nature/paysage", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Nature/paysage", "Description"), "Median Cut"] = 'background-color: lime'

    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Erreur moyenne par pixel"), "Median Cut"] = 'background-color: lightskyblue'
    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Erreur moyenne par pixel"), "Fourier RGB"] = 'background-color: lightcoral'
    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Description"), "Median Cut"] = 'background-color: lime'
    styles.loc[("Palette restreinte (motif répétitif, dessin simplifié)", "Description"), "Méthode Naive"] = 'background-color: lime'

    styles.loc[("Couleurs Vives", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Couleurs Vives", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Couleurs Vives", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Couleurs Vives", "Description"), "Median Cut"] = 'background-color: lime'
    styles.loc[("Couleurs Vives", "Description"), "Octree"] = 'background-color: lime'

    styles.loc[("Couleurs ternes", "Erreur moyenne par pixel"), "Median Cut"] = 'background-color: lightskyblue'
    styles.loc[("Couleurs ternes", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Couleurs ternes", "Erreur moyenne par pixel"), "Fourier RGB"] = 'background-color: lightcoral'
    styles.loc[("Couleurs ternes", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Couleurs ternes", "Description"), "Median Cut"] = 'background-color: lime'
    styles.loc[("Couleurs ternes", "Description"), "Méthode Naive"] = 'background-color: lime'

    styles.loc[("Texture fine", "Erreur moyenne par pixel"), "Median Cut"] = 'background-color: lightskyblue'
    styles.loc[("Texture fine", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Texture fine", "Erreur moyenne par pixel"), "Octree"] = 'background-color: lightskyblue'
    styles.loc[("Texture fine", "Erreur moyenne par pixel"), "Méthode Naive"] = 'background-color: cyan'
    styles.loc[("Texture fine", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Texture fine", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Texture fine", "Description"), "Median Cut"] = 'background-color: lime'
    styles.loc[("Texture fine", "Description"), "Octree"] = 'background-color: lime'

    styles.loc[("Architecture", "Erreur moyenne par pixel"), "Median Cut"] = 'background-color: lightskyblue'
    styles.loc[("Architecture", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Architecture", "Erreur moyenne par pixel"), "Méthode Naive"] = 'background-color: lightcoral'
    styles.loc[("Architecture", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Architecture", "Description"), "Median Cut"] = 'background-color: lime'

    styles.loc[("Architecture avec Filtre Sobel + contours", "Erreur moyenne par pixel"), "Octree"] = 'background-color: lightskyblue'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Erreur moyenne par pixel"), "Méthode Naive"] = 'background-color: lightskyblue'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Description"), "Fourier Grayscale"] = 'background-color: lime'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Description"), "Octree"] = 'background-color: lime'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Architecture avec Filtre Sobel + contours", "Description"), "Méthode Naive"] = 'background-color: lime'

    styles.loc[("Homme", "Erreur moyenne par pixel"), "Octree"] = 'background-color: lightskyblue'
    styles.loc[("Homme", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Homme", "Erreur moyenne par pixel"), "Median Cut"] = 'background-color: lightskyblue'
    styles.loc[("Homme", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Homme", "Erreur moyenne par pixel"), "Fourier RGB"] = 'background-color: lightcoral'
    styles.loc[("Homme", "Description"), "Octree"] = 'background-color: lime'
    styles.loc[("Homme", "Description"), "K-Means"] = 'background-color: lime'
    styles.loc[("Homme", "Description"), "Méthode Naive"] = 'background-color: lime'

    styles.loc[("Homme avec Flou gaussien", "Erreur moyenne par pixel"), "Octree"] = 'background-color: lightskyblue'
    styles.loc[("Homme avec Flou gaussien", "Erreur moyenne par pixel"), "K-Means"] = 'background-color: lightskyblue'
    styles.loc[("Homme avec Flou gaussien", "Erreur moyenne par pixel"), "Median Cut"] = 'background-color: lightskyblue'
    styles.loc[("Homme avec Flou gaussien", "Erreur moyenne par pixel"), "Fourier YCbCr"] = 'background-color: lightcoral'
    styles.loc[("Homme avec Flou gaussien", "Erreur moyenne par pixel"), "Fourier RGB"] = 'background-color: lightcoral'
    styles.loc[("Homme avec Flou gaussien", "Description"), "Octree"] = 'background-color: lime'
    styles.loc[("Homme avec Flou gaussien", "Description"), "Méthode Naive"] = 'background-color: lime'
    return styles

# Appliquer le style
styled_df = df.style.apply(highlight_custom, axis=None).pipe(style_full_separators)
display(styled_df)

# Amélioration : on évite les doublons et accélère l'initialisation avec sample (plus rapide que plusieurs choice)
def initialisation_centroide(liste_pixels, k):
    return random.sample(liste_pixels, k)

# Amélioration : évite l'utilisation coûteuse de min(distances) + index()
def assigner_cluster(liste_pixels, centroids, choix_distance=distance_euclid):
    clusters = [[] for _ in centroids]
    for pixel in liste_pixels:
        min_dist = float('inf')
        idx_min = 0
        for i, centroid in enumerate(centroids):
            d = choix_distance(pixel, centroid)
            if d < min_dist:
                min_dist = d
                idx_min = i
        clusters[idx_min].append(pixel)
    return clusters

# Recalcule les centroïdes à partir des clusters
# Amélioration : même logique, mais plus explicite et robuste
def recalcule_centroids(clusters):
    centroids = []
    for cluster in clusters:
        if cluster:
            r = sum(p[0] for p in cluster) // len(cluster)
            g = sum(p[1] for p in cluster) // len(cluster)
            b = sum(p[2] for p in cluster) // len(cluster)
            centroids.append((r, g, b))
        else:
            # Si un cluster est vide, on génère un centroïde aléatoire
            centroids.append((random.randint(0,255), random.randint(0,255), random.randint(0,255)))
    return centroids

def kmeans(image, k, max_iter=10, choix_distance=distance_euclid):
    W, H = image.size
    pixels = image.load()

    # On transforme l'image en liste plate de pixels
    liste_pixels = [pixels[x, y] for y in range(H) for x in range(W)]

    # Initialisation aléatoire des centroïdes
    centroids = initialisation_centroide(liste_pixels, k)

    for _ in range(max_iter):
        # Affectation des pixels aux centroïdes
        clusters = assigner_cluster(liste_pixels, centroids, choix_distance)

        # Recalcul des centroïdes à partir des clusters
        new_centroids = recalcule_centroids(clusters)

        # Si les centroïdes ne changent plus, on arrête l'algorithme
        if new_centroids == centroids:
            break

        centroids = new_centroids

    # Création d'une nouvelle image recolorisée
    new_image = Image.new("RGB", (W, H))
    new_pixels = new_image.load()

    # Amélioration : cache pour éviter de recalculer la distance pour des pixels identiques
    cache = {}

    for y in range(H):
        for x in range(W):
            pixel = pixels[x, y]
            if pixel in cache:
                couleur = cache[pixel]
            else:
                min_dist = float('inf')
                idx_min = 0
                for i, centroid in enumerate(centroids):
                    d = choix_distance(pixel, centroid)
                    if d < min_dist:
                        min_dist = d
                        idx_min = i
                couleur = centroids[idx_min]
                cache[pixel] = couleur
            new_pixels[x, y] = couleur

    return new_image

# Fonction récursive pour le découpage des pixels en utilisant Median Cut
def _median_cut_recursive(pixels, profondeur):
    # Cas de base : on renvoie la couleur moyenne du groupe
    if profondeur == 0 or len(pixels) == 0:
        if len(pixels) == 0:
            return [(0, 0, 0)]  # Sécurité si la liste est vide
        r = sum(p[0] for p in pixels) // len(pixels)
        g = sum(p[1] for p in pixels) // len(pixels)
        b = sum(p[2] for p in pixels) // len(pixels)
        return [(r, g, b)]

    # Calcul des étendues (amplitudes) de chaque canal (R, G, B)
    min_r = min(p[0] for p in pixels)
    max_r = max(p[0] for p in pixels)
    min_g = min(p[1] for p in pixels)
    max_g = max(p[1] for p in pixels)
    min_b = min(p[2] for p in pixels)
    max_b = max(p[2] for p in pixels)

    # Déterminer la composante avec la plus grande étendue
    ranges = [(max_r - min_r, 0), (max_g - min_g, 1), (max_b - min_b, 2)]
    _, channel = max(ranges)

    # Tri des pixels selon la composante choisie
    pixels.sort(key=lambda x: x[channel])

    # Découpage à la médiane
    median = len(pixels) // 2

    # Appels récursifs pour les deux moitiés
    return (
        _median_cut_recursive(pixels[:median], profondeur - 1)
        + _median_cut_recursive(pixels[median:], profondeur - 1)
    )

# Fonction principale
def median_cut(image, profondeur):
    px = image.load()
    W, H = image.size

    # Extraction des pixels dans une liste plate
    pixels = [px[x, y] for y in range(H) for x in range(W)]

    # Appel de la récursion Median Cut
    return _median_cut_recursive(pixels, profondeur)

Algorithme	Complexité mémoire	Estimation en octets	Éléments dominants
Méthode naïve	O(n)	~96n	Dictionnaire couleurs
Median Cut	O(n)	~76n	Liste de pixels + image
Octree	O(n)	~216n	Arbre Octree (noeuds)
K-Means	O(n)	~144n	Clusters (listes de pixels)

	Avantages	Inconvénients
Distance Euclidienne en RGB	Facile à implémenter Rapide à calculer	Ne correspond pas bien à la perception humaine (on perçoit certaines différences de couleurs plus fortement que d'autres)
Distance DeltaE76	Excellente qualité pour le regroupement de couleurs	Il faut convertir chaque couleur RGB en Lab (plus coûteux)
Distance DeltaE00	Précision pour juger si deux couleurs sont visuellement similaires	Plus complexe à implémenter Moins intuitif

		K-Means	Median Cut	Octree	Méthode Naive	Fourier YCbCr	Fourier RGB	Fourier Grayscale
Image	Critère
Portrait	Description	Ombres et couleurs respectées	Ombres et couleurs respectées	Manque de détails	Couleurs non fidèles	Couleurs non fidèles	Couleurs non fidèles
Portrait	Erreur moyenne par pixel	4.6	5.07	6.5	26.69	29.19	28.64
Nature/paysage	Description	Bon compromis entre respect des couleurs et des formes	Bon compromis entre respect des couleurs et des formes	Dégradés de couleurs respectés au détriment des formes,	Image non fidèle	Très bonne restitution des formes générales mais ajout de nouvelles couleurs	Forme générale respectée mais couleurs ternes
Nature/paysage	Erreur moyenne par pixel	7.23	8.11	9.92	15.61	20.78	23.28
Palette restreinte (motif répétitif, dessin simplifié)	Description	Respect des différentes tonalités de couleurs et des formes	Respect des différentes tonalités de couleurs et des formes	Uniformisation des couleurs de l'arrière-plan	Compromis formes/couleurs	Image de couleur quasi-uniforme / mauvaise définition des contours	Image de couleur quasi-uniforme / mauvaise définition des contours
Palette restreinte (motif répétitif, dessin simplifié)	Erreur moyenne par pixel	4.92 ; 1.73	5.24 ; 2.72	7.38 ; 3.88	8.1 ; 1.96	15.68 ; 13.4	18.93 ; 16.58
Couleurs Vives	Description	Fidèle et légère perte de contraste	Fidèle et légère perte de contraste	Très fidèle avec quelques déauts	Peu fidèle, palette terne	Image floue, non fidèle	Img fidèle mais plus fade
Couleurs Vives	Erreur moyenne par pixel	38.52	43.8	49.15	108.88	123.75	88.4
Couleurs ternes	Description	Très fidèle à l'image originale	Très fidèle	Fidèle mais moins de détails en arrière-plan	Image de type argentique	Couleurs non fidèles	Couleurs non fidèles
Couleurs ternes	Erreur moyenne par pixel	4.35	4.27	6.76	10.92	18.97	18.0
Texture fine	Description	Fidèle	Fidèle	Précision dans les détails extraordinaire	Uniformise l'image	Uniformise l'image	Uniformise l'image
Texture fine	Erreur moyenne par pixel	0.81	0.84	0.95	1.93	6.66	2.51
Architecture	Description	Très fidèle	Très fidèle, bonne nuance de couleurs	Palette terne mais image fidèle	Non fidèle, non respect de la forme générale	Forme restituée mais palette terne	Forme restituée mais palette terne
Architecture	Erreur moyenne par pixel	4.36	4.51	7.15	21.14	19.32	17.95
Architecture avec Filtre Sobel + contours	Description	Très fidèle	Fidèle mais moins de contraste	Très fidèle	Très fidèle	Image terne		Très fidèle
Architecture avec Filtre Sobel + contours	Erreur moyenne par pixel	0.0	2.46	0.0	0.0	10.05		5.07
Homme	Description	Très fidèle	Fidèle avec plusieurs défauts	Trsè fidèle mais forme floue	Style différent mais fidèle	Image floue, non fidèle	Image très floue, non fidèle
Homme	Erreur moyenne par pixel	5.26	5.76	6.83	12.95	20.52	21.02
Homme avec Flou gaussien	Description	Fidèle avec quelques défauts	Fidèle avec de nombreux défauts	Fidèle mais forme lisse	Style différent mais fidèle	Flou, non fidèle	Très flou, non fidèle
Homme avec Flou gaussien	Erreur moyenne par pixel	5.14	5.44	6.82	13.14	20.55	20.94

Introduction¶

Sommaire¶

Fonctions générales¶

Importation des modules¶

Création et enregistrement de l'image test¶

Récupération de toutes les couleurs constituant l'image et fréquences associées¶

Test de couleurs_presentes¶

Affichage de la palette¶

Test : affichage de la palette des 4 couleurs constitutrices de l'image test¶

Recoloriage de l'image¶

Test de la fonction recoloriage¶

Méthode de validation de notre approche¶

Calcul du score global d'erreur du recoloriage¶

Test de la fonction score sur notre carré test de 4 couleurs initialement¶

Affichage de la différence entre les deux images¶

Test de la fonction difference sur notre carré de 4 couleurs : pour notre palette de 4 couleurs¶

Complexités spatiale et temporelle¶

Génération d'une image de taille variable avec des couleurs aléatoires¶

Test de la génération aléatoire d'une image¶

Complexité temporelle¶

Test de la complexité temporelle¶

Complexité spatiale¶

Approche quantitative¶

Détermination de la complexité théorique¶

Méthode Naïve¶

Median Cut¶

Octree¶

K-Means¶

Fourier¶

Synthèse : complexité spatiale de nos algorithmes¶

Distances¶

Euclidienne¶

Test de la fonction distance euclidienne¶

Distance en espace CIELAB (Lab) : $\Delta E 76$¶

Test de la fonction distance $\Delta E 76$¶

Distance $\Delta E 2000$¶

Test de la fonction distance $\Delta E 2000$¶

Synthèse comparative des différentes distances¶

Méthode naïve¶

Chargement des images avec PIL¶

Choix d'une palette de k couleurs : la méthode naïve¶

Tri des couleurs par fréquence décroissante d'apparition et sélection des k couleurs de la palette¶

Application du recoloriage à l'image contenant le dégradé¶

Méthode de validation de notre approche¶

Calcul du score global d'erreur¶

Application de notre fonction différence au dégradé de couleurs¶

Quid d'augmenter le nombre de k couleurs arbitrairement ?¶

Median Cut Algorithm¶

Test de la fonction Median Cut et recoloriage¶

Octree Algorithm¶

Test de la méthode Octree¶

K-Means Algorithm¶

Test de la méthode K-Means¶

Traitement avec Fourier¶

Fourier en niveau de gris¶

Fourier sur YCbCr¶

Fourier en RGB¶

Traitement d'images par filtres¶

Test de la fonction conversion_gris¶

Flou gaussien¶

Test de la fonction somme_matrice¶

Test du flou gaussien¶

Filtres de type sobely3 et sobelx3¶

Amélioration des filtres Sobel¶

Test et application de nos filtres¶

Synthèse comparative des méthodes développées¶

Fonctions de synthèse¶

Portrait de Lovelace¶

Distance euclidienne¶

Distance $\Delta E 76$¶

Distance $\Delta E 2000$¶

Paysage¶

Distance euclidienne¶

Distance $\Delta E 76$¶

Distance $\Delta E 2000$¶

Motif répétitif¶

Distance euclidienne¶

Distance $\Delta E 76$¶

Distance $\Delta E 2000$¶

Festival¶